General Class Information Class Handouts Scores Assignments Reference Materials Lecture Notes

CSc 345 Analysis of Discrete Structures Fall 2024 Lester I. McCann, Ph.D.

The University of Arizona College of Science Department of Computer Science McCann's Home Page

General Class Information

• Class syllabus (general course information)
• D2L Site Mainly useful for textbook access.
• Class Q&A Board. We're using Piazza for class discussions this semester.
• Some thoughts about exams:
  • Characteristics of Good Exam Answers (suggestions on how to reply to short-answer exam questions)
  • Suggestions for Studying For and Taking Exams (what to do before and during an exam)
• Program Documentation and Development:
  • Programming Style Requirements (summary)
  • Toward Developing Good Programming Style (many documents here)
• A brief tutorial on using the turnin utility.

Class Handouts       (In case you lost your copy, or missed class)

• Syllabus Summary (2024-08-27)
• Programming Style Requirements (summary)
• Single-Source Shortest Path Algorithms (2024-10-01)
• Problems for Practice: Recurrence Relations (online only; 2024-10-24)
• Multiway External Merge Sort (2024-10-24)

Current Course Grades       (Updated after each exam has been graded)

• Current Grades (Updated: 2024-11-01 8:50 p.m.)

Assignments

• Homeworks:
  • Homework #1 Due: 2024-09-05
  • Homework #2 Due: 2024-09-26
  • Homework #3 Due: 2024-11-07
  
  
• Programs:
  • Program #1: The VIC (VIC InComplete) Cipher Due: 2024-09-19
    • The readVICdata.txt file mentioned in the handout.
  • Program #2: Bones Battle Due: 2024-10-17
    • Here's the executable version of Bones Battle so that you can play the game before you code the missing bits. Execution instructions are in the assignment handout, but, at least under Windows, I can run it by just double-clicking on the JAR file.
    • Here are the supplied Bones Battle files. Extract them into the same directory as the .java files you are writing and compile them all to complete the game.
  • Program #3: ColumnSort Due: 2024-10-31
    • Sample data files: prog03a.dat and prog03b.dat
    • ColumnSort.mp4 - a screen recording of an old Flash animation of Columnsort that you might find helpful (credit: Rachel Nehmer)
    • Timing2.java - a small demonstration of the use of nanoTime()
  • Program #4: They did the MASH ... Due: 2024-11-26

Reference Materials       (Pointers to additional information)

• The texts for this semester are two versions of what is basically the same book, both free:
  • CS3 Data Structures & Algorithms, by the OpenDSA Project. This is more recent, and has helpful interactive content, too, such as algorithm and data structure animations.
  • Data Structures and Algorithm Analysis by Clifford Shaffer, 2013, is the older static version, available as a 600-page PDF.
• LaTeX resources:
  • I've got a resource page for LaTeX for those of you who would like to use it for formatting your answers to homework assignments. (Last updated: July 2021)
  • Don't want to install LaTeX on your computer? Try Overleaf, a free (for personal use) online LaTeX editor.
  • Want help formatting equations in LaTeX? You might like this tool: LaTeX equation demo by MyScript
• Curious about what does and does not count as 'academic dishonesty'? My Academic Dishonesty Quiz might be an eye-opener!
• Example Programs
  • Topic 1: Review T01n01.java T01n02.java T01n03.java T01n04.java
  • Topic 2: Asympototic Analysis T02n01.java T02n02.java T02n03.java T02n04.c T02n05.java T02n06.java
  • Topic 3: Sorting T03n01.java T03n02.java
  • Topic 7: BSTs T07n01.java T07n02.java T07n03.java T07n04.java
  • General: Timing.java

Miscellaneous       (A place for stuff that doesn't really fit anywhere else)

• Academic Dishonesty Quiz Slides How well do you know the UA Code of Academic Integrity? Probably not as well as you should. Try this quiz to find out!
• CS2023's CS Curriculum Guidelines A joint work of the ACM and the IEEE Computer Society. The Algorithmic Foundations knowledge area (pages 87-100) details data structures, algorithms, and asymptotic complexity knowledge units, not all of which are covered in this class. The SDF (Software Development Fundamentals) area mentions data structure and algorithm basics as well.
• The Computer Science Lab Helpdesk has information on the department's computing equipment and services, including a link to change your CS account's password. You'll need to supply your NetID for access.
• Although the textbook has several algorithm animations, there are many others available. For example:
  • https://visualgo.net/bn/sorting -- traditional bar-height visualizations
  • https://imgur.com/gallery/voutF -- morolin's sorting visualization movie collection. Hard to follow when you first see them, because each movie has each algorithm running against itself. Also has some algorithm comparison videos.
  • The 1980 Sorting Out Sorting movie by Prof. Ronald Baecker (yes, it even has an IMDB entry) is a classic sorting algorithm visualization.
    • The full half-hour movie: https://www.youtube.com/watch?v=HnQMDkUFzh4
    • Too boring? Here's a 'compressed' (7:17) version of the movie: http://www.youtube.com/watch?v=gv0JUEqaAXo
    • Still too slow? Here's the exciting (?) concluding scene: https://www.youtube.com/watch?v=HnQMDkUFzh4&t=25m39s
  • https://www.youtube.com/user/AlgoRythmics -- AlgoRythmics, a collection of videos of sorting algorithms brought to life via a variety of dance forms. Not a good way to learn the algorithms, but still fun to watch.

Completed Slides and Guided Notes

• Completed Lecture Slides. I will be posting my annotated-in-class lecture slides soon after the end of each class.
  
  
  • Click here to access the completed lecture slides.


• Guided Notes. What follows are links to the 'guided notes' (the yet-to-be-annotated slides) that I have created so far. The idea is that you can print these and write your notes on them during lecture. These are formatted as PDFs with two slides per page, for ease of printing and to leave plenty of space for your notes.
  
  
  • Topic 0: Syllabus Overview
  • Topic 1: Review
  • Topic 2: Algorithm Analysis
  • More to come, time permitting!

---

Return to Ol' Doc McCann's Home Page

If you have any comments about this page, drop me a note at mccannl@acm.org