CSE 5311 Design and Analysis of Algorithms
Department of Computer Science and Engineering
Dr. Junzhou Huang


[ Administration | Course Description | Syllabus | Assignments | Other Information | Attention]

Administration

Course

CSE 5311 | Class Number: 93633
Lecture

ERB130 | Friday 1:00-3:50 PM
Instructor

Junzhou Huang | jzhuang@uta.edu | Office: ERB 650 | Office hours: Friday 3:50-5:50 PM (or by appointment)
Textbook

T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, Introduction to Alghorithms. 3nd edition, McGraw-Hill, 2009,
 
Prerequisites

All students are expected to have passed the courses CSE 2320 Algorithms and Data Structures and CSE 3315 Theoretical Computer Science or an equivalent before attending this course. Students are expected to have working experiences on software development, compilation process and programming in Standard C or Java.
GTA

Saiyang Na | sxn3892@mavs.uta.edu | Office: ERB 403 | Office hours: Friday 10:00am ~ 12:00pm (or by appointment)

Course Description

This course provides an overview of the Design and Analysis of Algorithms. Computer algorithms is at the heart of computer sciences. Algorithms are used everywhere, from operating systems to databases, to solving a variety of optimization problems. This course will cover all major areas of algorithms: sorting algorithms, greedy algorithms, graph algorithms, dynamical programming, maximum flow problems, string matching algorithms, geometric algorithms, and randomized algorithms. Besides above traditional algorithms, several state-of-art practical algorithms will be covered. Major ideas are introduced through examples and historical perspectives, so that students will have a grasp on the evolution and development of algorithms. Class projects are required to practice the algorithms learned in the class. After completing this course, students will have the ability to independently investigate a computational problem, design a practical algorithm to solve it and analyze the performance of the algorithm.

Grades

There will be homeworks, projects, 1 midterm, and 1 final exams. Course grades will be determined by the following weights:

Final letter grades will be assigned based on absolute percentage as follows:

where [ ] denotes inclusion and ( ) denotes exclusion. The instructor reserves the right to move the thresholds down based on the distribution of final percentages, but they will not move up.


Syllabus

  • Week 1
    • Aug. 25: Introduction (Slides) ; Algorithms and Growth functions (Slides) ;
  • Week 2
    • Sep. 01: Divide-and-Conquer (Slides) ; Master Theorem (Slides) ;
  • Week 3
    • Sep. 8: Fast Fourier Transform (Slides) ; Heapsort (Slides);
  • Week 4
    • Sep. 15: Quicksort (Slides) ; Sorting in Linear Time (Slides) ; (HW1 Due)
  • Week 5
    • Sep. 22: Median and Order Statistics (Slides) ; Binary Search Trees (Slides) ;
  • Week 6
    • Sep. 29: Red-Black Trees (Slides) ; Dynamic Programming (Slides) ;
  • Week 7
  • Week 8
    • Oct. 13: Recitation Class by GTA (Practice)
  • Week 9
    • Oct. 20: Midterm Exam (Chapter 1-4, 6-9, Chapter 12-13, Chapter 30)
  • Week 10
    • Oct. 27: Greedy algorithms (Slides) ; Greedy algorithms (Slides)
  • Week 11
    • Nov. 03: Graph Algorithms: BFS and DFS(Slides) ; Topological Sort (Slides) (HW3 Due)
  • Week 12
    • Nov. 10: Minimum Spanning Trees (Slides) ; Single-source Shortest Path (Slides)
  • Week 13
    • Nov. 17: All-pairs Shortest Path (Slides) ; Maximum Flow (Slides) (HW4 Due)
  • Week 14
    • Nov. 24: No class due to Thanksgiving Holidays
  • Week 15
    • Dec. 01: Project Due and Class Presentation (HW5 Due)
  • Week 16
    • Dec. 08: Final Exam 11:00am-1:30pm (ERB130)

Assignments

Homeworks, Programming Assignments and other material will be made available here. They are due at the beginning of class.

Homework 1 : Textbook, 2.2-1(page.29), 2.3-3 (page 39), 2.1 (page39), 3-1, 3-2, 3-6, 4.5-1(a, b), 4.5-4, 4-1(a,b), 30-3

Homework 1 Solution [PDF]

Homework 2 : Textbook, 6.2-6, 6-2, 7.2-2, 7-1, 8.1-3, 8-3, 9-1, 12.3-3, 13.1-4, 13.1-5

Homework 2 Solution [PDF]

Homework 3 : Textbook, 15.1-1, 15.1-2, 15.1-3, 15.2-4, 15.2-5, 16.1-1, 16.1-2, 16.1-3, 16.2-4, 16.3-1

Homework 3 Solution [PDF]

Homework 4 : Textbook, 22.1-7, 22.2-5, 22.2-7, 22.4-3, 22-1, 23.1-4, 23.1-10, 24.1-3, 24.3-3, 24.3-4

Homework 4 Solution [PDF]

Homework 5: Textbook, 25.1-3, 25.1-5, 25.2-6, 25.3-4, 25.3-6, 26.1-6, 26.2-1, 26.2-8, 26.2-9, 26.3-3

Homework 5 Solution [PDF]

 

Assignment Strategies:
a) You are expected to submit all assignments on the due date. Type up is preferred.
b) Assigments should be turned in before or in the class or TA office hour on due date.
c) Your name and ID number should appear in your homework.

Projects

Implementing and comparing the following algorithms. How their running times change with respect to data size? How their speed compare to each other in the cases with different data size? Can you improve their running time with your discovery? Which one is better in terms what conditions?

Each group has two members at most. Each group should choose at least one project from the following projects. Each group should submit a project report and do a presentation in the class. Each member in the group should mention her/his contribution respectively.

1. Implement and compare the following sorting algorithm:
● Mergesort
● Heapsort
● Quicksort
● Insertion sort
● Radix sort


2. Implement and compare the following search algorithm:
● Linear search
● Binary search in sorted array.
● Binary search tree
● Red-Black Tree


3. Implement and compare the following shortest paths algorithm for weighted graph and unweighted graph:
● Breadth-first search (unweighted graph)
● The Bellman-Ford algorithm
● Dijkstra’s algorithm


4. Implement and compare the following Minimum Spanning Trees algorithms:
● Kruskal algorithm
● Prim algorithm


5. Implement and compare the following max flow algorithms:
● The Ford-Fulkerson method
● Push relabel algorithm
● The relabel-to-front algorithm

 


Other Information

Americans with Disabilities Act

The University of Texas at Arlington is on record as being committed to both the spirit and letter of federal equal opportunity legislation; reference Public Law 93112 -- The Rehabilitation Act of 1973 as amended. With the passage of new federal legislation entitled Americans With Disabilities Act - (ADA), pursuant to section 504 of The Rehabilitation Act, there is renewed focus on providing this population with the same opportunities enjoyed by all citizens. As a faculty member, I am required by law to provide "reasonable accommodation" to students with disabilities, so as not to discriminate on the basis of that disability. Student responsibility primarily rests with informing faculty at the beginning of the semester and in providing authorized documentation through designated administrative channels.

Academic Integrity

It is the philosophy of The University of Texas at Arlington that academic dishonesty is a completely unacceptable mode of conduct and will not be tolerated in any form. All persons involved in academic dishonesty will be disciplined in accordance with University regulations and procedures. Discipline may include suspension or expulsion from the University. "Scholastic dishonesty includes but is not limited to cheating, plagiarism, collusion, the submission for credit of any work or materials that are attributable in whole or in part to another person, taking an examination for another person, any act designed to give unfair advantage to a student or the attempt to commit such acts." (Regents' Rules and Regulations, Part One, Chapter VI, Section 3, Subsection 3.2, Subdivision 3.22)

 

Grade Appeal Policy

If you do not believe a grade on a particular assignment is correct, you may appeal the grade in writing (email) within 5 class days. Grade appeals must be ppealed to the appropriate GTA firstly, then to your instructor if necessary. Please refer to the UTA Catalog for the detailed guide of grade appeals.

 

Student Support Services Available

The University of Texas at Arlington provides a variety of resources and programs to help you develop academic skills, deal with personal situations, better understand concepts and information related to their courses, and achieve academic success. These programs include major-based learning centers, developmental education, advising and mentoring, personal couneling, admission and transition, and federally funded programs. Students requiring assistance academically, personally, or socially should contact the Office of Student Success Programs at 817-272-6107 or visit www.uta.edu/resources for more information and appropriate referrals.

 

Drop Policy

The university withdrawal policy will be strictly adhered to. Up to the initial withdrawal date, all students will receive a W. The drops after the final withdrawal date will not be approved normally unless the student has already shown to complete the course work satisfactorily, etc.

 

Missed Exams, Quizzes, and Makeup Work

Ecacuation Map

https://www.uta.edu/campus-ops/ehs/fire/Evac_Maps_All/Evac_CRB/Evac_CRB_114.pdf

 

Attention

Students are responsible to check this webpage frequently! The instructor reserves the right to modify and/or change the above information about this course with reasonable notification to students.