Data Structures - Announcements; Wolfgang Bein

Wolf Bein

CS 302 Introduction to Data Structures

ANNOUNCEMENTS

Posted 08-15-19:
The pages for this course are now ready. The syllabus is subject to change.

Posted 08-15-19:
If you do not have an account in the lab yet: Here is the account application.

Posted 08-27-19:
For assignment 1: Complex numbers explained. Also, headers, output, and code snippets for assignment 1.

Posted 08-27-19:
Seiden's Theoretical Computer Science Cheat Sheet.

Posted 08-27-19:
Current Reading: 1.4 - 1.7 in the 30 page handout, Chapter 2.

Posted 09-01-19:
Message from Ed Jorgensen:
--------------
FYI - We have some slots for TA this semester. If you are interested in being a CS Tutor/Lab monitor for the Fall 2019 semester, please fill out the link below:
Fall 2019 Undergraduate Application Form.
Feel free to forward this to anyone who might be interested.
Thanks!
--------------

Posted 09-13-19:
Linked Lists: Reading is 3.5 and 3.6, see 45 page handout , the code is here list_class.cxx
How to generate random numbers.

Posted 09-13-19:
This is how to print the list:


for(ni=the_List.begin(); ni!=the_List.end(); ni++)
   {
         cout << *ni << " ";

   }

Posted 09-13-19:

For assignment 3, here is how to measure the run of your program:

You need to use the command time. The syntax for using time is
time ./a.out
The output for time will have three lines like these.
real 59.95
user 55.24
sys 0.09
Use is the one called `user'. (55.24 in the example below.)
The other ones (real, sys) take operating system overhead
into account.

Posted 09-13-19:
Here is the Master Theorem.

Posted 09-16-19:
A quick clarifcation regarding overloading of the ++ operator:


iterator& operator++();   // ++it

overloads the prefix version
and


iterator operator++(int); // it++

overloads the postfix version

Posted 09-18-19:
The Tuesday TA office hours are shifted 15 minutes earlier: Now they are: Tuesday, 10:45 am - noon.

Posted 09-26-19:
Current Reading: Chapter 3.

Posted 09-26-19:
Exam 1 will be on Friday, October 11.

Posted 09-26-19:
More on Postfix Expressions.

Posted 09-26-19:
Note that substraction and division do not commute, ab/ means a/b and not b/a (similarly ab- means a-b).
Here are a few more examples to test your program:
4572+-*$ -16
34+2*7/$ gives 2
57+62-*$ gives 48
42351-+*+$ gives 18
42+351-*+$ gives 18

Posted 09-26-19:
Here is a simple function to convert a character, which represents a number to a n integer value:


int CharToInt(const char c)


{



    switch (c)



    {


    case '0':
        return 0;


    case '1':
        return 1;


    case '2':
        return 2;


    case '3':
        return 3;


    case '4':
        return 4;


    case '5':
        return 5;


    case '6':
        return 6;


    case '7':
        return 7;


    case '8':
        return 8;


    case '9':
        return 9;


    default:
        return 0;
    }


}

Posted 09-26-19:
Current Reading: 4.1, 4.2.

Posted 09-30-19:
Reminder: The first midterm is on Friday, October 11.
Reading (study guide) for the first midterm.

Study Guide
Chapter 1 (Math and Code review)
Chapter 2 (Algorithmic Complexity).
Chapter 3: 3.1,3.5 (Lists), 3.6 (Stacks), 3.7 (Queues).
Chapter 4: 4.1, 4.2 (Trees)
Chapter 7: 7.1, 7.2 (Insertion Sort).
Review assignments 1 - 5.

Posted 09-30-19:
Here are the solutions for assignment 4.

Posted 09-30-19:
Here is the dot-h file TaskTree.h for assignment 6. Additionally, here is main.cxx.
You may modify the files.
Here is a code snippet to set up the tree and another code snippet which shows you how to print out such a tree in preorder. Here are constructors.

Posted 10-18-19:
There is no class on October 25 due to Nevada day, instead as indicated on the syllabus here are the intructions for our October 25 virtual meeting:
1. Read 4.5 (Splay Trees) in our text book.
2. Study the following Splay Tree Notes.
3. Look at 11.5 which discusses amortized run time analysis for splay trees.
4. Have questions ready for our next class meeting
Note that next week's Thursday office hour (October 24) is canceled.

Posted 10-29-19:
Here are the 2-3 Tree Slides.

Posted 10-29-19:
Here is the Binary Search Tree code and dsexceptions.h.

Posted 11-04-19:
Milestone design component (roughly one page in length):
- design document
- data structure used and how they were implemented; explain why the use of these structures fosters efficiency.
- what machine used to compile and run
Here are prointers for a good design document. As discussed our design documents will be somewhat simpler.

Posted 11-14-19:
Current Reading: 6.1-6.4, 6.8,6.9, 7.5-7.7.

Posted 12-03-19:
Fun with sorting: Dance routines for
mergesort, quicksort, and heapsort. As well Super Mario Heapsort Here slowsort visualization.

Posted 12-03-19:
Notes on Graphs.

Posted 12-03-19:
Here is an example graph and the text file text file for Assignmemt 11.

Posted 12-05-19:
The final is on Friday, in TBE B-178 12/13/2019, Friday, 10:10AM - 12:10PM. It is comprehensive.
Reading:
Chapter 1
Chapter 2
Chapter 3
Chapter 4: 4.1, 4.2, 4.3, 4.4, 4.6, 4.7,
Chapter 5: 5.1, 5.2, 5.3, 5.4, 5.5
Chapter 6: 6.1, 6.2, 6.3, 6.4, 6.8
Chaper 7: 7.1, 7.2, 7.3, 7.6, 7.5, 7.7, 7.9
Chapter 8: 8.1, 8.2, 8.3, 8.4
Chapter 9: 9.1, 9.2, 9.5, 9.6
Review assignments 1 - 11.