CSc345 - Analysis of Discrete Structures

 -  Summer 2018

Instructor and Teaching Assistants

Alon Efrat,

alon@cs.arizona.edu

Gould Simpson 742

Office Hours: Office Hours:  Mon-Wed at 2:30 at GouldSimpson 701 or my office

Could also schedule a meeting via skype (alontucson @ skype)

Alex Koltz

akoltz@email.arizona.edu

Gould Simpson 733B

Office Hours: Mon Wed 12:00 - 3:00

Or a skype meeting

Homeworks  link

        

Course Description:

                                                 

The emphasis of this course is on data structures and efficient implementations of algorithms that use them. In the process of learning and practicing methods of data structures and algorithm design, we will see many examples of important algorithms.

                                                

Some of the data structures we will study are stacks, queues, trees, tries, and heaps. Algorithms considered will include sorting, searching, and hashing. We will also learn about graphs, graph algorithms, asymptotic notation, and algorithm analysis.

                                                                                           

                        

                                

                                        

Syllabus                                                 

The course is organized into six parts. After each topic below are the relevant chapter numbers from the text. Note that not all material covered in class will be in the textbook (e.g., Skip Lists). The syllabus below is only an outline and very likely to change.

I Introduction slides         

Definitions of trees, heights, and number of nodes.  

Algorithms (1, 2): notion of algorithm, measuring time and space

Analysis (3, 4): asymptotics, sums, recurrences

II Sorting        

  1. Sorting by divide and conquer:
  1. Merge sort (2):  slides  
  2. Quicksort  Quicks slides video don’t forget the 5-random keys method. (CLRS Chapter 6)

Heap sort (6): slides Insertion Sort  slides  and Swap Sort

  1. Counting sort and Radix Sort (8): sorting integers in a bounded range  video slides  video

III Data structures

  1. Link lists and SkipLists slides 
  2. Heaps (priority queues)  slides (CLRS Chapter 6)        
  3. Line Sweep Algorithm part1  part2  slides 

 

IV Search trees

  1.  Basic operations: search, insertion, deletion, predecessor, and successor worst-case efficiency through height balancing,   video.
  1. Note how we delete a key which is not a leaf.  
  1. AVL trees slides1, slides2,  video2  video1  and
  1. After the basic definitions, we proved that the height of an AVL tree is O(log n). Insertions is performed as in a binary balanced search trees, and then we traverse the tree upward, update heighs fields, and if needed, use one of the 4 rotations (LL, LR, RL or LL) to fix the balance.
  2. Deletions are handled as in an unbalanced BST. However we do not cover the re-balancing that might be needed.  

  1. B-trees and 2-3 trees. Definitions, insertions and deletions. Video 1 (start at 40:00) , video2  video3 2-3 trees and (a,b) B trees and B+ trees.
  2. Quad Trees video. slides,  

------------------- Material for the final starts here ----------------------

  1. Hashing

(basic techniques, your will see more in cs445) Hashing (i) and Hashing (ii).  slides  (CLRS)

  1. 1D and 2D range Trees, video1  kd-trees. slides 

  

 

VI Graphs  

Representation (22): basic concepts, adjacency matrix, adjacency list.        Searching (22): depth-first and breadth-first search of undirected and directed graph slides and  lecture. 

 

Prim Algorithm for finding a Minimum Spanning Tree. Slides: Prim Algorithm for finding a Minimum Spanning Tree,  Lecture: Intro to MST.

                        Huffman codes (CLRS 16.3)

                        Finding maximum matching in a bipartite graph lecture 

Finding topological order of vertices of a directed graph (DAG)

lecture  slides

 

Homeworks

Posting date

Theoretical homework 1

 

Theoretical homework 2

 6/23/18

Theoretical homework 3

 7/9/18

Theoretical homework 4

 7/25/18

Implementation Hw 1

 

Implementation Hw 2

 

                                        

                                

                        

                

Course Prerequisites or Co-Requisites

One of the following is required, with a grade C or better:  CSC 245, MATH 243, or MATH 323.  Also, one of the following is required, with a grade C or better: CSC 127B or CSC 227.

 

Course Objectives and Expected Learning Outcomes

The student will:

Absence and Class Participation Policy

Students are expected to attend class. It is the student's responsibility to be aware of material discussed in class in case of absence. Use of laptops and similar devices is allowed, but only to the level that your attention is focused on the discussion in class.The UA’s policy concerning Class Attendance, Participation, and Administrative Drops is available at http://catalog.arizona.edu/2015-16/policies/classatten.htm 

The UA policy regarding absences for any sincerely held religious belief, observance or practice will be accommodated where reasonable: http://policy.arizona.edu/human-resources/religious-accommodation-policy.

Absences pre-approved by the UA Dean of Students (or dean’s designee) will be honored. See http://uhap.web.arizona.edu/policy/appointed-personnel/7.04.02 

Required Texts or Readings

Thomas H. Cormen, Charles E. Leiserson, Ron L. Rivest, and Clifford Stein, Introduction to Algorithms, McGraw-Hill, Boston.

Optional Texts

                                                

Assignments and Examinations: Schedule/Due Dates

Homework: There are about seven homeworks, which occur roughly each week.  At least two of the homeworks involved programming.  The grade of the lowest theoretical homework score will be dropped from calculation of the final grade.

Midterm:          July 9, 2018 

Final:                 Last day of class

 

Grading Scale and Policies

The course numeric_final_grade is computed based on the the formula:

46%   Homework grade

21%   MidTerm exam grade

21%   Final exam grade

12%   Max{MidTerm_exam_grade, Final_exam}

Grade Distribution for this course:​​​

A: ≥ 90%

B: ≥ 80%

C: ≥ 70%​

D: ≥ 60%​

E: ≤ 59%

Requests for incomplete (I) or withdrawal (W) must be made in accordance with University policies, which are available at http://catalog.arizona.edu/2015-16/policies/grade.htm#I and http://catalog.arizona.edu/2015-16/policies/grade.htm#W, respectively.

 

Homeworks Ethics and Instructions

On homework, you are expected to think about and try to solve the problem for yourself. You may discuss general ideas with friends, but your solutions must be written up separately and represent individual work, and if ideas were developed during a collaborative discussion, list clearly with whom you brainstormed ideas. Use of solutions from previous offerings of the course (at UofA or any other university) is not permitted. Five points will be deducted per day for lateness, and late homework cannot be turned in after solutions have been discussed in class.

Use D2L to submit your homework. They should be .pdf files. You could use LaTeX, Word, Google Doc, etc, or you could write using your handwriting, scan and submit. It is your responsibility to verify that homework is legible. Please do not submit paper solutions. Neatness, and especially conciseness, is required to earn the highest marks. If you cannot solve a problem, state this in your write-up, and write down only what you know to be correct; rambling at length about ideas that don't quite work may cause additional points to be deducted.

Department of Computer Science Code of Conduct

The Department of Computer Science is committed to providing and maintaining a supportive educational environment for all. We strive to be welcoming and inclusive, respect privacy and confidentiality, behave respectfully and courteously, and practice intellectual honesty.  

Disruptive behaviors (such as physical or emotional harassment, dismissive attitudes, and abuse of department resources) will not be tolerated.  The complete Code of Conduct is available on our department web site.  We expect that you will adhere to this code, as well as the UA Student Code of Conduct, while you are a member of this class.

Classroom Behavior Policy

To foster a positive learning environment, students and instructors have a shared responsibility. We want a safe, welcoming, and inclusive environment where all of us feel comfortable with each other and where we can challenge ourselves to succeed. To that end, our focus is on the tasks at hand and not on extraneous activities (e.g., texting, chatting, reading a newspaper, making phone calls, web surfing, etc.)

Inclusive Excellence is a fundamental part of the University of Arizona’s strategic plan and culture. As part of this initiative, the institution embraces and practices diversity and inclusiveness.  These values are expected, respected and welcomed in this course.

Elective Name and Pronoun Usage

This course supports elective gender pronoun use and self-identification; rosters indicating such choices will be updated throughout the semester, upon student request.  As the course includes group work and in-class discussion, it is vitally important for us to create an educational environment of inclusion and mutual respect.

Threatening Behavior Policy

The UA Threatening Behavior by Students Policy prohibits threats of physical harm to any member of the University community, including to oneself. See http://policy.arizona.edu/education-and-student-affairs/threatening-behavior-students.

Accessibility and Accommodations

Our goal in this classroom is that learning experiences be as accessible as possible. If you anticipate or experience physical or academic barriers based on disability, please let me know immediately so that we can discuss options. You are also welcome to contact the Disability Resource Center (520-621-3268) to establish reasonable accommodations. For additional information on the Disability Resource Center and reasonable accommodations, please visit http://drc.arizona.edu.

If you have reasonable accommodations, please plan to meet with me by appointment or during office hours to discuss accommodations and how my course requirements and activities may impact your ability to fully participate. Please be aware that the accessible table and chairs in this room should remain available for students who find that standard classroom seating is not usable.

Code of Academic Integrity

Students are encouraged to share intellectual views and discuss freely the principles and applications of course materials. However, graded work/exercises must be the product of independent effort unless otherwise instructed. Students are expected to adhere to the UA Code of Academic Integrity as described in the UA General Catalog. See http://deanofstudents.arizona.edu/academic-integrity/students/academic-integrity.

Selling class notes and/or other course materials to other students or to a third party for resale is not permitted without the instructor’s express written consent. Violations to this and other course rules are subject to the Code of Academic Integrity and may result in course sanctions. Additionally, students who use D2L or UA e-mail to sell or buy these copyrighted materials are subject to Code of Conduct Violations for misuse of student e-mail addresses. This conduct may also constitute copyright infringement.

UA Nondiscrimination and Anti-harassment Policy

The University is committed to creating and maintaining an environment free of discrimination; see http://policy.arizona.edu/human-resources/nondiscrimination-and-anti-harassment-policy

Our classroom is a place where everyone is encouraged to express well-formed opinions and their reasons for those opinions. We also want to create a tolerant and open environment where such opinions can be expressed without resorting to bullying or discrimination of others.

Additional Resources for Students

UA Academic policies and procedures are available at http://catalog.arizona.edu/2015-16/policies/aaindex.html

Student Assistance and Advocacy information is available at http://deanofstudents.arizona.edu/student-assistance/students/student-assistance

Confidentiality of Student Records  

http://www.registrar.arizona.edu/ferpa/default.htm

Subject to Change Statement

Information contained in the course syllabus, other than the grade and absence policy, may be subject to change with advance notice, as deemed appropriate by the instructor.