Course Syllabus
Course Staff & Schedule
Instructor
Hari Sundar
🏢 2692 WEB ☎ 8015859913 ✉ hari@cs.utah.edu
Office hours: Tue 12:302:30pm, WEB 2692  https://utah.zoom.us/my/hsundar
Lecture
T,Th 10:4512:05pm
Teaching Assistants  See Getting Help for help hours.
 Raine Burkett
 Gaurav Dhir
 Anuja Kampalli
 Aaron Schindler
 James Youngblood
Learning Goals
We will study the algorithms, the ideas behind the algorithms, and the limitations of the algorithms that are used to solve a variety of programming problems that span the field of computer science. After we review some material from CS 2100 and CS 2420, we will study divideandconquer algorithms, graph decomposition, paths in graphs, number theory algorithms, greedy algorithms, dynamic programming, linear programming, the theory of NPcompleteness, and approaches to coping with NPcomplete problems.
You will learn how to determine, both analytically and experimentally, the time and space complexity of algorithms, and you will learn the practical implications of complexity results. You will learn how to apply classical algorithm design techniques to obtain new algorithms, and how to reason about the correctness of algorithms. You’ll learn about a variety of problems for which efficient algorithms exist, learn about a variety of problems for which no efficient algorithms have been discovered, and learn why most computer scientists believe efficient algorithms may not exist for those problems.
When you finish the course, you will be be familiar with a broad range of algorithms, you will be equipped to read and exploit the extensive literature on algorithms, you will have the mathematical background to understand and reason about algorithms, and you will know how to analyze algorithms.
Course Overview
Prerequisite: Basic algorithms and data structures. As this course has a prerequisite of CS 2420, we will not start from scratch with algorithms and data structures. We expect you to be familiar with basic
 algorithms for sorting (selection sort, insertion sort, quicksort, mergesort),
 algorithms for searching lists (linear search, binary search),
 data structures for representing lists and sets (array lists, linked lists, binary search trees, hash tables),
 abstractions of data structures (lists, queues, stacks, sets, maps), and
 asymptotic complexity analysis (bigO bounds).
If you do not have this background, you should not take this course.
Prerequisite: C++,C#, Python or Java.
Since this course has a prerequisite of both CS 2420 and CS 3500, we will assume that you know how to program in either C# or Java. You will be writing one program as part of each weekly assignment. Beyond this, it is essential that you be comfortable programming so that you can understand how what we will be discussing can be realized as programs.
If you are not a competent programmer, you should not take this course.
Prerequisite: Discrete math.
Since this course has a prerequisite of CS 2100, we will not start from scratch with the discrete math that underlies complexity analysis, algorithm design, and correctness reasoning. A partial list of topics from discrete math with which we expect you to be familiar are:
 notation.
 Exponents, logarithms, summations, and products.
 Proof techniques, including proof by contradiction and mathematical induction.
 Sets, relations, functions, trees, and graphs.
If you do not have this background, you should not take this course.
Course Organization
Prerequisites. The prerequisites for this class are programming mastery (demonstrated by taking CS 3500), an introductory algorithms and data structure course (such as CS 2420), and a course in discrete mathematics (such as CS 2100). See the previous section for a discussion of specific topics with which you must be familiar.
Text. The required text is Algorithms by Dasgupta, Papadimitriou, and Vazirani. The text covers a wide range of algorithms in the course of 10 chapters. Because the text is not encyclopedic, we will be able to cover almost all of it. It is also relatively inexpensive. Get a copy and read it!
Lectures. We will meet for lecture twice a week for 80 minutes. I will use a combination of a laptop and a (digital) whiteboard during lectures. I will use the laptop to present programming examples and perform demonstrations; I also make use of slides. I will make the laptopbased examples available online, but you will need to take notes if you want to keep track of what I write on the board or say out loud.
There is no substitute for attending lectures; I expect all students to attend all lectures. You will not be able to completely reconstruct lectures after the fact from the slides and examples that I post online. There is no substitute for participating actively in lecture; I expect all students to put away their electronic devices and pay attention. You may think you’re good at multitasking, but I disagree.
Consulting. All of the course staff (instructor and teaching assistants) will be available outside of formal classes to answer your questions and help with problems. We will post the consulting schedule on Canvas as soon as it is finalized.
Reading. The Canvas home page links to a schedule that will show the topic and reading assignment for each lecture. Following each lecture, I will update this calendar to reflect what was actually covered in lecture that day. I will also add links to any online material that I used. By the end of the semester, the schedule will contain a record of everything we covered.
Problem Sets. Each Thursday (except before the midterm and final) I will post a problem set on Canvas. Each problem set will consist of a collection of written problems (due the following Thursday at 11:59 p.m.) and possibly one programming problem (due the following Friday at 11:59 p.m.).
You will submit your written problems via Canvas. There will be three types of written problems:
 Multiple choice and short answer quizzes are used to assess your understanding of particular algorithms or to lead you through the analysis of algorithms. You will take these quizzes inside of Canvas, and they will be graded automatically.
 Essay quizzes are used to pose questions that require up to a few paragraphs to answer. You will take these quizzes inside of Canvas, and they will be graded by the TAs.
 Essay assignments are used to pose questions that take more than a few paragraphs to answer. You will submit solutions to these assignments by uploading professionally formatted PDF documents. (Scanned handwritten solutions will not be accepted.) Essay assignments will be graded by the TAs.
You will submit your solutions to programming problems to the online Kattis system, which will automatically grade it. Your grade will be based on whether your program is correct and acceptably efficient. The system will accept programs written in a large variety of languages. Details on using Kattis will be included in the problem sets.
Grade Appeals. We will do our best to grade each submission within five working days of its due date. If you believe that a mistake has been made in grading an essay quiz or written assignment, contact the TA who graded it. If you believe that a mistake has been made in the automatic grading of a program or quiz, contact the TA who is supervising the grading of that submission. In either case, we must receive your appeal within five working days of your receipt of your grade. Do not make your appeal by attaching a note to your assignment or its grading report within Canvas. We are not notified about such notes, and they are easy to overlook.
Late Policy. You can submit a solution to a written problem up to three days late; you can submit a solution to a programming problem up to two days late. We are generally forgiving about submissions that are only a few minutes late, but don’t push it! Over the course of the semester you can accumulate a maximum of 15 late days, summed over all written and programming problems. Once you reach that limit, we will no longer accept your late submissions.
Exams. There will be a midterm and a final. The midterm will be on Thursday February 29 in place of lecture, and the final will be in the usual lecture room on Wednesday, May 1, 10:30am12:30 pm. Both exams will be closed book, but you will be able to bring one (midterm) or two (final) sheets of notes.
Grading. A weighted average will be calculated based on your quiz/assignment average (50%), your midterm exam grade (20%), and your final exam grade (30%). Grades will be assigned on a curve consistent with the weighted averages of the students.
If your exam average (40% midterm, 60% final) is not a passing grade, the highest grade you can receive in the class is a D+.
Getting Help and Information. Canvas will contain a variety of resources, including course staff consulting hours, discussion forums, problem sets, examples from lecture, grades, and reading. All of the course staff will be available outside of formal classes to answer your questions and help with problems. We will post the consulting schedule to Canvas as soon as it is finalized. We encourage you to seek us out whenever you need help, advice, or encouragement.
When we wish to communicate with the entire class, we will post announcements to piazza. Be sure to set your piazza notification preferences so that you receive announcements.
Please use piazza to ask questions that are likely to be of general interest to other students. This can be done by posting to "Entire Class". For example, if you don’t understand an assignment, have a question about some aspect of C#, or want help with using Visual Studio, post to the forum. That way, other students will be able to benefit from the answer. You should, of course, search through old postings before posting a new question. If you are asking something specific and want to include your solution or code, please only post to "Instructors". It is also helpful to select the appropriate folder while posting.
When you wish to contact me and the TAs, use Piazza. Please use Piazza (sent only to instructors) to ask questions that are either confidential, concern a specific solution to an assignment, or are unlikely to be of general interest to other students.
If you need to contact one of us individually (for example, to ask about a grade), send a message via Piazza.
Classroom Demeanor
It is becoming increasingly common for students to treat classroom lectures as just one more mode of input to juggle via multitasking. Students commonly play games, send text messages, monitor their Facebook page, read email, and chat with friends while simultaneously trying to follow the lecture.
My classroom is not a YouTube video. I run an interactive lecture, and it is your opportunity to understand and come to grips with the material in real time. Your goal should be to concentrate, participate in the class, become engaged with the lecture, and leave with a better understanding of the material. You’ll have to put a lot of mental effort into the lecture in order to accomplish this. You can’t do this while playing with your phone.
Your choices of how to conduct yourself in lecture impact the other students in class. Your neighbor in the lecture hall will have a hard time concentrating if you’re playing a game or carrying on a conversation. No one will appreciate it if you make a habit of asking questions that are necessary only because you weren’t paying attention because you were working on an assignment for another class.
Cooperation vs. Cheating
Working with others on assignments is a good way to learn the material and we encourage it. However,there are limits to the degree of cooperation that we will permit. When taking an online quiz or an inclass exam, you must work completely independently of everyone else. Any collaboration here, of course, is cheating.
You must limit your discussions with other students of programs or written assignments to a highlevel discussion of solution strategies. If you do collaborate with other students in this way, the solution that you submit must identify the students and describe the nature of the collaboration. The solution that you hand in for programs or written assignments must be written in your own words. If you base your solution on any other written solution, regardless of the source, you are cheating.
We do not distinguish between cheaters who copy others’ work and cheaters who allow their work to be copied.
If you have any questions about what constitutes cheating, please ask.
If you cheat, you will be given an E in the course and your case will be handled as detailed here.
Students with Disabilities
Reasonable accommodation will gladly be provided to the known disabilities of students in the class. Please let the instructor know of such situations as soon as possible. If you wish to qualify for exemptions under the Americans With Disabilities Act (ADA), you should also notify the Center for Disabled Students Services, 160 Union Building.
Tentative Course Coverage

Introduction & Review
 Linear search and binary search
 Selection sort and insertion sort
 Lists, sets, and maps
 Arrays, linked lists, binary search trees, and hash tables
 Asymptotic analysis:
 Experimental analysis

Divide and Conquer Algorithms
 Representing big integers
 Arithmetic on big integers
 Recurrence relations
 Master Theorem
 Karatsuba multiplication
 Quicksort and mergesort
 Quickselect
 Blended algorithms
 Lower bound on comparisonbased sorting

Graph Decomposition
 Types of and uses for graphs
 Graph representations
 Depthfirst search on undirected graphs
 Depthfirst search on directed graphs
 Topological sorting
 Strongly connected components

Graph Search
 Breadthfirst search
 Shortest paths problem
 Dijkstra’s algorithm
 BellmanFord algorithm
 Shortest paths on DAGs
 Analysis of Dijkstra’s algorithm
 Binary heaps and heapsort

NumberTheoretic Algorithms
 Modular arithmetic
 Modular addition and multiplication
 Modular exponentiation
 Euclid’s algorithm and the Extended Euclid algorithm
 Density of prime numbers
 Primality testing
 RSA encryption algorithm
 Encryption in ecommerce

Greedy Algorithms
 Simple greedy algorithms
 Minimum spanning trees
 Prim’s algorithm
 Kruskal’s algorithm
 Union/find data structure
 Set cover problem
 Proofs of correctness of greedy algorithms

Dynamic Programming
 Problems where the greedy approach fails
 Rod cutting problem
 Memoization vs. tablebased methods
 Knapsack problem
 Minimum edit distance problem
 Palindromic subsequence problem

Linear Programming
 Applications of linear programs
 Simplex algorithm
 Duality

NPCompleteness
 Search problems
 P, NP, and the question P =NP?
 Polynomialtime reductions
 NPcomplete problems
 Proving NPcompleteness via reduction
 Proving NPcompleteness from first principles

Coping with NPCompleteness
 Intelligent backtracking
 Branch and bound
 Approximation algorithms