Course Syllabus

Course Staff & Schedule

Instructor

​ Hari Sundar

​ 🏢 2692 WEB ☎ 801-585-9913 ✉ hari@cs.utah.edu

​ Office hours: Tue 12:30-2:30pm, WEB 2692  - https://utah.zoom.us/my/hsundar 

Lecture

T,Th  10:45-12:05pm

Teaching Assistants - See Getting Help for help hours.

  1. Raine Burkett
  2. Gaurav Dhir
  3. Anuja Kampalli
  4. Aaron Schindler
  5. 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 divide-and-conquer algorithms, graph decomposition, paths in graphs, number theory algorithms, greedy algorithms, dynamic programming, linear programming, the theory of NP-completeness, and approaches to coping with NP-complete 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

  1. algorithms for sorting (selection sort, insertion sort, quicksort, mergesort),
  2. algorithms for searching lists (linear search, binary search),
  3. data structures for representing lists and sets (array lists, linked lists, binary search trees, hash tables),
  4. abstractions of data structures (lists, queues, stacks, sets, maps), and
  5. asymptotic complexity analysis (big-O 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:

  • LaTeX: \mathcal{O} 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 laptop-based 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 multi-tasking, 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:

  1. 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.
  2. 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.
  3. 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:30am-12: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 multi-tasking. Students commonly play games, send text messages, monitor their Facebook page, read e-mail, 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 in-class 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 high-level 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

  1. 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: LaTeX: \mathcal{O}, \Omega, \Theta
    • Experimental analysis

  2. 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 comparison-based sorting

  3. Graph Decomposition

    • Types of and uses for graphs
    • Graph representations
    • Depth-first search on undirected graphs
    • Depth-first search on directed graphs
    • Topological sorting
    • Strongly connected components

  4. Graph Search

    • Breadth-first search
    • Shortest paths problem
    • Dijkstra’s algorithm
    • Bellman-Ford algorithm
    • Shortest paths on DAGs
    • Analysis of Dijkstra’s algorithm
    • Binary heaps and heapsort

  5. Number-Theoretic 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 e-commerce

  6. 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

  7. Dynamic Programming

    • Problems where the greedy approach fails
    • Rod cutting problem
    • Memoization vs. table-based methods
    • Knapsack problem
    • Minimum edit distance problem
    • Palindromic subsequence problem

  8. Linear Programming

    • Applications of linear programs
    • Simplex algorithm
    • Duality

  9. NP-Completeness

    • Search problems
    • P, NP, and the question P =NP?
    • Polynomial-time reductions
    • NP-complete problems
    • Proving NP-completeness via reduction
    • Proving NP-completeness from first principles

  10. Coping with NP-Completeness

    • Intelligent backtracking
    • Branch and bound
    • Approximation algorithms