11:0012:15 TR 110 Eppley 
Dr. David Reed
203D Hitchcock x2583 DaveReed@creighton.edu 
Text: Introduction to the Design and Analysis of Algorithms, 3rd ed.,
Anany Levitin, Addison Wesley, 2012.
** Free PDFs of this text can be found online. **
Prerequisite: CSC 321
This is the fourth course in the computer science sequence, building upon the concepts and skills acquired in the first three. Whereas CSC 221 and CSC 222 focused on the design of simple algorithms and CSC 321 focused on fundamental data structures, this course considers both facets of problem solving and their interrelationships. In order to solve complex problems efficiently, it is necessary to design algorithms and data structures together since the data structure is motivated by and affects the algorithm that accesses it.
As the name of the course suggests, special attention will be paid to analyzing the efficiency of specific algorithms, and how the appropriate data structure can affect efficiency. Specific topics covered in this course will include: advanced data structures (e.g., trees, graphs and hash tables), common algorithms and their efficiency (e.g., binary search, heapsort, graph traversal, and bigOh analysis), and problemsolving approaches (e.g., divideandconquer, backtracking, and dynamic programming).
The specific goals of this course are:
Students will complete 57 assignments throughout the semester. Most assignments will involve the design and implementation of Java programs that appropriately utilize data structures and algorithms. Assignments may also contain written components, for example, justifying design choices or analyzing program behavior. Late assignments will be accepted up to 7 days after their due date, with a maximum score of 75%. Beyond 7 days, late submissions will not be accepted. There will be 810 module quizzes, one 75minute midterm exam, and a cumulative final exam (see the schedule below for exam dates).
There is no specific attendance policy for the course, although it is expected that absences will leave the student unprepared for tests and assignments. Quizzes and tests will not be rescheduled except in extreme circumstances. However, the lowest quiz grade will be dropped. The final grade for the course will be based on the following weightings:
module quizzes/exercises  05 % 
57 programming assignments  45 % 
75minute midterm exam  20 % 
100minute final exam  30 % 
At the minimum, standard grading cutoffs for the final average will apply. That is, 93% guarantees an A, 90% an A, 87% a B+, 83% a B, 80% a B, etc. Depending on class performance, some shifting of grades (in an upward direction only) may occur as final letter grades are assigned.
It is expected that all students check their Creighton email accounts regularly. Official announcements, such as assignment revisions or class cancellations, will be distributed through Creighton email.
Creighton's policy on cheating and plagiarism is spelled out in the the Student Handbook, with college procedures available online. In addition to this, the following guidelines hold pertaining to programs. Programs are to be the sole work of the student  collaboration on the design or coding of a program is not allowed. You may not seek help on homework assignments from others, from online sources, or from AIbased tools. Questions regarding homework assignments should be directed at the instructor only. If there is any question about the source of work, the student may be called upon to explain their work to the instructor.
Violations of this collaboration policy will be dealt with severely, with possible outcomes including failure in the course. In the case of programming assignments, you are encouraged to start early so that there is time to seek help from the instructor as the need arises.
Date  Topic  Readings  Assignments 

Aug 20 22 
Course overview. (pptx) Java/Data Structures review: (pptx) 
321 material 
HW1: due 9/5 
27 29 
OO design, data structures, efficiency. Brute force: (pptx) 
Ch 12 

Sep 3 5 
exhaustive search, generateandtest, Knapsack problem, algorithms+dataStructures. 
Ch 3 
HW2: due 9/19 
10 12 
Decreaseandconquer: (pptx) byconstant, byconstantfactor, byvariableamount. 
Ch 4 

17 19 
Divideandconquer: (pptx) sorting examples, tree recursion. 
Ch 5 

24 26 
Transformandconquer: (pptx) problem reduction, space vs. time, BoyerMoore. 
Ch 6 

Oct 1 3 
Greedy algorithms: (pptx) scheduling, Prim's, Dijkstra's. 
Ch 9 

8 10 
review MIDTERM EXAM 


15 17 
FALL BREAK  NO CLASS  
22 24 
midterm and HW review Backtracking: (pptx) 
Ch 12.1 

29 31 
Nqueens, blob counting, Boggle, Sudoku, branch & bound, game trees, alphabeta. 
Ch 12.2 

Nov 5 7 
Dynamic programming: (pptx) topdown vs. bottomup, World Series puzzle, 
Ch 8 

12 14 
Floyd's algorithm, caching. Algorithm case studies: (pptx) 


19 21 
Google search, stable matching. Analyzing problems: (pptx) 
Ch 10 

26 28 
lower bounds, decision trees, problem reduction. Complexity & computability: (pptx) 
Ch 11 Ch 12.3 

Dec 3 5 
complexity theory, decidability, P vs. NP. course overview 


Dec 9
 FINAL EXAM Mon, 10:0011:40 
Creighton University may modify, suspend, or postpone any and all activities and services immediately and without notice because of force majeure causes beyond Creighton's control and occurring without its fault or negligence including, but not limited to, acts of God, fire, war, governmental action, terrorism, epidemic, pandemic, weather, national emergencies, or other threats to the safety of students or staff. Creighton may, at its option, alter the academic schedule or provide alternate instruction modalities to meet course objectives and competencies and program outcomes, including, but not limited to, distance or remote learning, until such time as Creighton determines normal operations may resume safely.