- Instructor: Badri Adhikari
- Email: adhikarib@umsl.edu
- Class meets:
Tuesdays 8:20PM - 9:35PM(synchronously via Zoom) - Office hours: Tuesdays 1:45 PM to 3:45 PM (or by appointment)
- This course covers analysis of time and space complexity of iterative and recursive algorithms, design of data structures for efficient performance, mathematical modeling, dynamic programming, divide and conquer strategies, greedy algorithms, a collection of graph algorithms, linear and integer mathematical programming, and NP-Completeness. [3 credit units].
- Graduate Standing in CS
CLRS 3rd Edition (ISBN 978-0-262-03384-8 or ISBN 978-0-262-53305-8); at amazon.
-
Chapter 3 - Growth of Functions
- 3.1 Asymptotic notation
- 3.2 Standard notations and common functions
-
Chapter 4 - Divide-and-Conquer
- 4.1 The maximum-subarray problem
- 4.2 Strassen’s algorithm for matrix multiplication
- 4.3 The substitution method for solving recurrences
- 4.4 The recursion-tree method for solving recurrences
- 4.5 The master method for solving recurrences
-
Chapter 15 - Dynamic Programming
- 15.1 Rod cutting
- 15.2 Matrix-chain multiplication
- 15.3 Elements of dynamic programming
- 15.4 Longest common subsequence
-
Chapter 16 - Greedy Algorithms
- 16.1 An activity-selection problem
- 16.2 Elements of the greedy strategy
- 16.3 Huffman codes
-
Chapter 17 - Amortized Analysis
- 17.1 Aggregate analysis
-
Chapter 22 - Elementary Graph Algorithms
- 22.1 Representations of graphs
- 22.2 Breadth-first search
- 22.3 Depth-first search
-
Chapter 23 - Minimum Spanning Trees
- 23.1 Growing a minimum spanning tree
- 23.2 The algorithms of Kruskal and Prim
-
Chapter 24 - Single-Source Shortest Paths
- 24.1 The Bellman-Ford algorithm
- 24.2 Single-source shortest paths in directed acyclic graphs
- 24.3 Dijkstra’s algorithm
-
Chapter 25 - All-Pairs Shortest Paths
- 25.1 Shortest paths and matrix multiplication
- 25.2 The Floyd-Warshall algorithm
-
Chapter 26 - Maximum Flow
- 26.1 Flow networks
- 26.2 The Ford-Fulkerson method
- 26.3 Maximum bipartite matching
-
Chapter 34 - NP-Completeness (skip proofs)
- 34.1 Polynomial time
- 34.2 Polynomial-time verification
- 34.3 NP-completeness and reducibility
-
Chapter 35 - Approximation Algorithms (skip proofs)
- 35.1 The vertex-cover problem
- 35.2 The traveling-salesman problem
- 35.3 The set-covering problem
- Keep yourself out of plagarism; Read UMSL's Policy; Our
turnitintool automatically checks for plagarism; Here is an example. - Lecture recordings, audio or video, are not permitted.
- You are recommended (but not required) to use Python3 for all of your homeworks and project. If you have a reason to use a different programming language (for example if your background is in C++ or Java), please send me an email and I can approve you to use a language of your choice.
- You can request a maximum two-day extension on any homeworks - for up to two submissions.
- If you email me a few hours before a deadline and I don't reply you immediately, and if you have not used your two-day extensions, you can assume that the extension is granted automatically.
- Once you use your extension days, late submissions will get no points.
The finals for this course will be in the form of a oral test, via Zoom one-on-one meetings. Each meeting may be up to 60 minutes long. Although some oral questions may check your understanding of the concepts, questions on the oral test will mostly focus on the details. Questions in the oral test will be from your own homework submissions. I will randomly pick one of your homework submissions, and ask you some details. Some students who have done exceptionally well may be exempt from the oral test. I will send an email to you if you are exempt, you cannot email and ask to be exempt. Closer to the finals week, you will be able to sign-up to select a time that works for you. Here is an example question:
- In your homework number 3, in paragraph 5, you discuss X and Y. Please mention the purpose of X.
- Attendance will be recorded sometimes.
- In the semester long-project you are expected to demonstrate an implementation of some practical application of algorithms. You are free to work on "any" project related to any of the algorithms we discuss in class. There are no specific requirements.
- Here is an example project by a student who took this course in Fall 2018 - MAZE-A-TRON game using BFS report
- There will be some homeworks from each chapter that we cover. Many of the homeworks will require you to implement algorithms. Some homeworks will require you to trace an algorithm (in paper) and submit your solution. You can take a picture of your solution and submit in Canvas.
- Homeworks (including programming homeworks) = 50 points
- Project = 10 points
- Final oral exam = 40 points
- 1 bonus point to everyone who complete the course evaluation survey (please email me once you submit the survey)
