ASU Ira A. Fulton Schools of Engineering
Kevin Burger

CSE294 Special Topics: Algorithmic Problem Solving


Disclaimer: this web page is the official syllabus for the course; paper copies will not be distributed. During the semester, changes may be made to the syllabus. If the change is significant, notification will be given in class, and an announcement will be made in Blackboard. Minor editing changes (spelling errors, grammar) will not be announced. The student is responsible for reading this syllabus at the beginning of the semester to acquaint himself or herself with the course policies, and for checking the syllabus periodically throughout the semester for relevant information.

Spring 2017—Course Information

Lecture Section 24701
Date & Time MW 4:35–5:50
Location BYENG 361
Instructor Kevin Burger
UGTA Maxfield Lehman

Course Description

Problem solving is at the core of computing and being able to derive effective solutions to programming problems is a skill that all computing students must master. Many students struggle in computing, and specifically, programming courses, because their problem solving skills are not well-developed. The focus of this course will be to improve students' analytical and problem solving skills by discussing numerous problems which are amenable to a computing solution. We shall design algorithmic solutions to the problems using well-known problem solving techniques. Algorithms may be documented using a variety of tech­niques, including flowcharts and pseudocode. We will implement programming solutions to some of these algorithms using low-syntax, low-learning curve pro­gramming languages, e.g., Python. This course is appropriate for any computer science, computer systems engineering, informatics, and software engineering student who desires to become a better problem solver and improve his or her programming skills.

This is a special topics course, meaning that it is not a cataloged course but may become one some day. The prerequisites are (MAT243 concurrent enrollment OR MAT243 completed) AND ((CST200 OR CSE205) AND with a grade of C or higher)). Three (3) credit hours. Some lecture, but mostly lab work.

Course Objectives

  1. Improve the students' problem solving skills.
  2. Write and design algorithms using well-known design documentation techniques, including flowcharts and pseudocode.
  3. Learn to read and comprehend algorithms that solve programming problems.
  4. Implement programming solutions for algorithms using Python.
  5. Improve the students' testing skills using black box testing.

Major Topics

This is a list of possible topics for the course in alphabetical order. We may not cover all of these topics and there may be some topics we cover that were not listed here at the beginning of the course.

  1. Depth-First Search with Backtracking
  2. Brute force, exhaustive search
  3. Combinations and permutations
  4. Constraint Satisfaction Problems (CSP)'s
  5. Decomposition and Divide and Conquer
  6. Memoization
  7. Graph problems
  8. Graph traversal: depth first, breadth first
  9. Python programming
  10. Recursion
  11. Top down and bottom up design
  12. Trees and tree traversal problems
  13. Algorithmic Time Complexity and Big O Notation

Office Hours & Support

The instructor will be available during his office hours to answer any questions you may have about the course, the material, or the projects. I'm a friendly guy (except when I'm not), and willing to talk with you and help you as much as I can, so stop by if you want, but please be aware that I also teach other courses and have other duties as well, so I am quite busy. When you come in for help, please be prepared to ask pointed and specific questions about what you do not understand or are having difficulty with. It is next to impossible for me to help you if you come in and say, "I don't understand anything." Also, a final word of advice. I may not be available as much as you would like the day before or the day an assignment is due. I will give you plenty of time to complete the assignments as long as you start working on them well before the deadline. This will give you ample time to meet with me or the UGTA to discuss your questions as you are working on the assignment. Start early!

We have an undergraduate teaching assistant (UGTA) assigned to the course: Maxfield Lehman (294@maxfieldlehman.com). His duties will be to assist me in teaching the course and he will be available for two weekly office hours in the BYENG 214 computer lab, where he will be available to help you with your assignments. Max's office hours will be MoTu 3:30–4:30, right before class. Max will also be the grader for the course, so when submitting assignments for grading, do what you can to keep the man happy. This includes carefully following the assignment submission instructions.

Course Materials & Resources

The website you are currently viewing is the main website for this course (I will refer to it as the course website), and most course information will be available here (e.g., lecture notes, assignment documents, exams, source code files, etc). I use Blackboard for: (1) posting important announcements; (2) student submission of assignment files; (3) posting homework and exam solutions and grading rubrics; and (4) posting scores in the Blackboard Grade Center.

Assessment

Various methods will be used to present the material and assess the student's understanding and comprehension.

Reading Assignments

We do not have a textbook, so data structures and algorithms textbook' materials and various online sites will be used as resources. The student may be asked to read information on these websites prior to class so he/she will be ready to participate in the in-class activities.

Attendance

There is a strong and well-established correlation between class attendance, learning, and performance; therefore, regular class attendance and participation is expected. I intend to begin class each day at 4:35 (give or take a few minutes) and I want you to be present and ready at that time. Because I intend for this class to be more "hands-on" than your average computer science class (think of this as a lab), I will take daily attendance. There are 29 class days (lectures) and you will earn 2 pts each day for being present when attendance is taken (if you are late, arriving after attendance has been taken, you will earn 1 pt). With 29 lectures there will be a total of 58 attendance points to be earned; however, when calculating your attendance percentage, denoted a in the course percentage formula below, I will divide the sum of your attendance points by 48, with the result not to exceed 100%. Essentially, this permits you to miss five lectures without it affecting your grade.

Homework Assignments

There will be h homework assignments (likely 5 to 8) which will involve designing and documenting algorithms and implementing some of those algorithms in Python. There may be short deadlines for some of the homework assignments, e.g., an assignment might be given Monday that requires a pseudocode solution to be submitted before class on Wednesday so that you can work on the Python implementation on Wednesday. At the end of the semester a homework percentage, denoted h in the course percentage formula below will be computed as the sum of your earned homework points divided by 0.9hp where hp is the total number of homework points to be earned. This means I am dropping 10% of the homework points which will help you out if you miss an assignment or score very poorly on one. Your homework assignment percentage with bonus credit is limited to a maximum of 100%.

Note: In cases of academic integrity violations—when the student is assigned a score of 0 on the homework assignment—no homework points will be dropped and your homework assignment percentage will be calculated as the sum of all earned homework assignments scores divided by hp.

Examinations

There will be two homework assignments that will count as the midterm and final exams. These "exams" will consist of more exercises than the other homework assignments and will contain exercises that review some of the exercises in the homework assignments leading up to the exam. The exams will be take-home. The midterm exam assignment will be assigned around the midpoint of the semester (around lecture 14 on 27 Feb) and the final exam will be assigned around a week before classes end, with lecture 29 on 28 Apr. You will be given at least one week to complete the exams. Each exam will be worth 100 pts.

Calculating Final Letter Grades

Your final letter grade will be based on your final course percentage,

FCP = ceiling[ (a × 10%) + (h × 60%) + (m × 15%) + (f × 15%) ]

Where a is your attendance percentage, calculated as described in the Attendance section above; h is your homework assignment percentage, calculated as described in the Homework Assignments section above; m is your midterm exam score; and f is your final exam score. Final letter grades are assigned per this table,

FCP Letter Grade
FCP ∈ [98, 100] A+
FCP ∈ [85, 98) A
FCP ∈ [70, 85) B
FCP ∈ [55, 70) C
FCP ∈ [40, 55) D
FCP < 40 E

Note: At the end of the semester, when assigning letter grades, the lower bound of each of the above ranges may be lowered, e.g., the lower bound for an A might be changed from 85% to 75%, with subsequent changes in the lower bounds of the other ranges. The only guarantee is that the lower bounds will not be raised.

Academic Misconduct

In general, the instructor believes learning is a collaborative activity, that students learn best when they work together, and that students should be encouraged to learn from and teach each other. These activities would include working together on assignments, discussing solutions to assignments and exams, and jointly studying for exams. In completing the assignments, student-pair collaboration is strongly encouraged and will be permitted as long as each member of the pair contributes equally to the work. Collaboration is only acceptable between members of the same pair-team; inter-team collaboration is forbidden and violators may be sanctioned. Collaboration on examinations is not permitted; each exam must be completed by the individual student. Failure to abide by these rules will result in a score of zero being assigned to one or both members of the team (i.e., if I have a reasonable hunch that one student did all of the work on an assignment and the other student simply put his/her name on it, then the student who did all of the work will receive the assignment score and the other student will be given a score of zero).

Note: See the Assessment section concerning how academic integrity violations are handled for homework assignments. In general, for the first AIP violation on a homework assignment, the student(s) will be assigned a score of 0 and the violation will not be reported to the Dean's office as long as the student does not wish to appeal the instructor's decision. If the student wishes to appeal the decision, then it must be reported to the Fulton Dean's office so the regular AIP appeal process can be followed. For the second AIP violation on a homework assignment, the student will again be assigned a score of 0 and the offense will be reported to the Fulton Dean's office. For the first AIP violation on an exam, the student will be assigned a score of 0 and the offense will be reported to the Dean's office. You should know that a second AIP violation which is reported to the Dean's office (in any course during your study at ASU, not just this one) and is upheld upon appeal will generally result in the student being expelled from the Fulton Schools of Engineering for at least one year.

You are strongly encouraged to acquaint yourself with the ASU Academic Integrity Policy

Classroom Behavior

The ASU Student Services Manual (SSM 201-10) permits the instructor to withdraw a student from a course for disruptive behavior with a mark of W (withdrawal) or E (failure). Note that "disruptive behavior" is defined by the instructor, not by the University or the student. Violation of conventional and acceptable classroom behavior will result in the offender being asked to exit the classroom and notification of the offense to the Fulton Schools of Engineering's Dean's Office. If required, Campus Security will be called. A warning may or may not be provided.

Requirements for Success in this Course

The instructor assumes that you are mature and responsible adults, that you are enrolled in this course because you wish to learn the material, that you will read any assigned readings before class begins, that you will come to class prepared to discuss the reading and ask questions, that you will complete the assignments to the best of your ability on time, that you will actively participate in class discussions, and that you will ask questions about material you find confusing. The instructor believes that college students must be actively involved in their own learning process, that they cannot just sit and listen to lectures and expect to learn the material, that one of the purposes of college education and the Arizona State University mission is for the student to self-develop skills such as problem solving, independent learning, critical thinking, and effective written and spoken communication. To succeed in this course you must:

Having said all that, I want you to know that I care about all of my students and their education. I want all of you to succeed, to feel you have gained something from the course, to have some fun in the process, and I will do all I reasonably can to assist you in your efforts!

Statement on Accommodations

The Disability Resource Center (480-965-1234; Matthews Center; email: drc@asu.edu) is the central location for students requiring accommodation. Any student requiring accommodation must contact and register with the Center before any accommodation requests can be granted by the instructor. If you require accommodation, please contact the DRC as soon as possible so the instructor can work with you to ensure your success.

Title IX

Title IX is a federal law that provides that no person be excluded on the basis of sex from participation in, be denied benefits of, or be subjected to discrimination under any education program or activity. Both Title IX and university policy make clear that sexual violence and harassment based on sex is prohibited. An individual who believes they have been subjected to sexual violence or harassed on the basis of sex can seek support, including counseling and academic support, from the university. If you or someone you know has been harassed on the basis of sex or sexually assaulted, you can find information and resources at http://sexualviolenceprevention.asu.edu.

Schedule

Links and Documents

ASU Links

Spring 2017 Academic Calendar
Spring 2017 Final Exam Schedule
My ASU
My ASU Courses (Blackboard)

Data Structures and Algorithms References

Algorithms, etc. - by Jeff Erickson
Data Structures and Algorithm Analysis, v3.2 - by Clifford Shaffer
Algorithms and Data Structures - by Melhorn and Sanders
Matters Computational - by Jorg Arndt

Homework Assignments

Homework Assignment 1
Homework Assignment 2
Homework Assignment 3
Homework Assignment 4

Notes

Algorithms, Software Design, Pseudocode, and Testing (Rev 1.2)
Brute Force Search (Rev 1.2)
Divide and Conquer (Rev 1.1)
Introduction to Python (Rev 1.4)

Online and Offline Python Development

Below is a list of online Python development tools. I cannot recommend any one of these over the others because I have not really used any them enough, but I like the looks of the one from Coding Ground. It appears to have enough features to make it useful but no so many that it is overly complicated. For a list of offline Python IDE's, check out this list at wiki.python.org. I have been using the Python 3 interpreter on Linux with IDLE. It is not as full-featured as some of the others but it is simple to use.

Cloud9 - Full-featured. Requires an account.
Code Linkster - Requires an account.
Codenv - Full-featured. Requires an account. Looks expensive.
Codepad - QAD (Quick and Dirty) programming. About as simple as it gets. Allows saving of files.
Code Skulptor - QAD programming. Allows saving of files.
Coding Ground - QAD programming. Provides a Bash shell interface.
ideone - QAD programming.
Learn Python - QAD programming with good tutorials.
Python Anywhere - Requires an account.
Python Fiddle - Simple cloud IDE.
Python Tutor - This one is cool as it permits visual tracing of code during execution.
Repl.it - QAD programming.
Skulpt - QAD programming.
Source Lair - Full-featured. Requires an account.
rextester - QAD programming.
Try Python! - QAD programming.

Programming Problem Solving Sites

ACM-ICPC Live Archive
CodingBat - Practice writing Python or Java code
DM:OJ - Don Mills Online Judge
GeeksForGeeks - A computer science portal for geeks.
Google Code Jam 2017 - Big prizes. Registration begins 7 Mar 2017.
HackerRank - Permits Python submissions
Internet Problem Solving Contest
LeetCode Online Judge - Permits Python submissions
P3G - PEG Online Judge
Project Euler - One of my favorite problem solving sites. Most problems have a mathematical basis.
Sphere Online Judge - Another favorite. Permits Python submissions
UVa Online Judge and udebug.com - Similar to the ACM-ICPC Live Archive

Python References (Tutorials, Books)

Functional Programming in Python - David Mertz, O'Reilly, 2015
How To Make Mistakes in Python - Mike Pirnat, O'Reilly, 2015
Python Documentation - The official Python 3.x documentation
The Python Tutorial - The official Python 3.x tutorial
Python Programming Tutorial - YouTube (by thenewboston)
Python Tutorial - Codecademy.com
Python Tutorial - TutorialsPoint.com
Problem Solving with Algorithms and Data Structures Using Python - by Brad Miller and David Ranum
Python Tutor - by Philip Guo. Permits visualization of a Python program during execution.
Rosetta Code - How do I do x in programming language y?
Think Python: How to think like a computer scientist, 2nd Ed - By Allen Downey

Source Code and Design Files

hangman.zip - Python implementation of the classic Hangman game
prime2-100.py - Prints all prime numbers in [2, 100].
stack.py.zip - A stack class using a list and object composition