Trees and Tree Algorithms
Trees are everywhere in IT. In Web Page Design I, students start out learning about the Unix filesyste, which is a tree, and half-way through the course learn about the DOM, another tree.
In this course we focus specifically on a specific kind of tree called a binary tree. Binary trees are very useful, and the fact that they have at most two children makes them easier to study than more general trees.
Read chapter 6: Trees and Tree Algorithms from our text, and complete the Self Checks on pages 193, 197, and 219, and as many of the Discussion Questions and Programming Excercises on pages 232-234 as time permits.
Last Weeks Before Senior Experience
With two weeks left until senior experience, there is not enough time for an
indepth exploration of the remaining topics in our course. I would argue that
the most effective strategy given our current reality would be to use the
last two weeks to become familiar with the key ideas from the course,
so that should you decide to pursue further study of computer science in the
future, you will at least have been exposed to the
big idea in a
data structures and algorithms course.
To that end, please complete the following this week:
- Read section 5.3: Sorting (pages 163-180) in our text.
- Type in and run the example code from this section, adding it to your GitHub repository for the course.
- Complete the Self Check exercises on page 181.
- Complete questions 5 through 8 in the Discussion Questions on pages 182-183.
Next week I'll add the last assignment from chapter 6.
Week Ten: April 24 to 28
Since it doesn't appear anyone completed the assignment from last week, we should continue to work on that assignment this week. To further explore hash functions, let's begin with the following:
- Add a body to the following function that will make the doctests pass:
def char_counts(s): """ Return a list containing counts of the number of occurances of each ASCII character in s. >>> result1 = char_counts("abbcccddddeeeeeffffff") >>> len(result1) 256 >>> result1[96:105] [0, 1, 2, 3, 4, 5, 6, 0, 0] >>> result2 = char_counts("AACEEEGIIJLLL") >>> result2[64:78] [0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 1, 0, 3, 0] >>> result3 = char_counts("this is seriously silly") >>> result3[ord('t')] 1 >>> result3[ord('i')] 4 >>> result3[ord('2')] 5 """
- How did what you just did relate to hash functions as discused in our text?
- Download a copy of alice_in_wonderland.txt.
- Write a program that counts the occurance of each character in Alice in Wonderland and nicely display's the results.
After completing this, go back and finish the tasks from last week.
Week Nine: April 18 to 21
This week we begin the study of search and sorting algorithms.
Read sections 5.1 and 5.2 from our text (pages 147 to 163). Complete the Self Check questions on pages 150, 153, 159-160, the Discussion Questions numbers 1 to 4 on page 180, and Programming Exercises numbers 1 to 7 on pages 183-184.
Week Eight: April 3 to 7
Your goal this week should be to complete Chapter 4: Recursion from our
text, including the Discussion Questions and Programming
Exercises at the end of the chapter. You should include screenshots in your
journal displaying running versions of the visualization programs from the
sierpinski and the
You should also be able to write the
cleanup.py programs described
Week Seven: March 27 to 31
This week we study a new topic:
recursion. Recursion is
both facinating and elegant, so pay close attention to the
presented in this chapter. This is more than a one week assignment, but I'm
not sure where the mid point is, so I ask you all to begin chapter 4 and to
move as far as you can with the time available. Document your learning, and
I'll use your journals next weekend as a guide for setting expectations for the
Please also read over the section on recursive data structures and recursion beginning with Recursive data structures from Beginning Python Programming for Aspiring Web Developers. We will be spending a lot of time with recursive data structures when we study trees in chapter 6.
Week Six: March 20 to 24
Complete Chapter 3: Basic Data Structures, sections 3.7 to 3.10, from our text. These sections discuss aspects of the very important list ADT.
You should complete all remaining discussion questions and programming exercises at the end of the chapter. I will provide you with additional practice problems that could serve as quiz questions for an end of chapter quiz to be taken next week.
Week Five: March 13 to 17
Complete Chapter 3: Basic Data Structures, sections 3.5 to 3.6 on queues and deques, from our text.
Complete the following exercises (found at the end of the chapter):
- Discussion Question 6 (page 113).
- Programming Exercises 5 to 9 (pages 113 to 114).
Week Four: March 5 to 10
Complete Chapter 3: Basic Data Structures, sections 3.1 to 3.4, from our
text. Each of you will need a GitHub repositor for your assignments. If
you haven't created it already, you could call it
csc202. Be sure
to link to it from your weekly journal.
Complete the following exercises (found at the end of the chapter):
- Discussion Questions 1 to 5 (pages 112-113).
- Programming Exercises 1 to 4 (page 113).
In addition to completing the exercises in the chapter and putting your solutions in your github repository, you should provide a detailed description of ADT and the Stack ADT. Look at the National Institute of Standards and Technology (NIST) presentation of the stack ADT. How does it differ from the one in our text?
Create a class named
NISTstack that implements the stack ADT as
presented by NIST. Choose one of the exercises completed in this section
and reimplement your solution using a
Week Three: February 26 to March 3
Complete Chapter 2: Algorithm Analysis from our text. In addition to completing the exercises in the chapter and putting your solutions in your github repository, you should provide a detailed description of Big-O notation together with specific examples of algorithms that run in constant time, logrithmic time, linear time, log linear time, and quadratic time. Provide links to other resources you looked at in addition to our text to gain an understanding of this fundamental computer science concept.
Weeks One and Two: February 12 to 24
Welcome to Computer Science II! In this course we will study data structures and algorithms. In many ways this will be closer to a course in high level mathematics than it is to a computer programming class. In fact, we will only be using Python as a tool to study interesting mathematical objects (data structures) and processes (algorithms), rather than as an end in itself.
That said, you will learn a lot of Python along the way, and we will make use of several tools that professional software developers and others use every day, beginning day one with your introduction to distributed version control.
Please complete each of the following before you come to class on Monday:
- If you don't already have one, create an account for yourself on Github.
- Complete the Try Git tutorial, creating your first git repository for our warehouse inventory system.
- Create a repository on github for your InventoryTracking system. Be prepared to share this repository when you come to class on Monday.
Your weekly journal should be completed five days per week, so if you are absent for any reason, you still need complete your work for this class. The weekly journal should available oy Monday with your plan for the week, and completed and ready for weekly evaluation each Friday.
Computer Science II is a data structures and algorithms class with learning outcomes as described in the course content summary. Since we are a small class filled with mature, dedicated, and responsible students, the process we will use this semester is self-guided study with weekly progress evaluation.
Each Monday you will create a new journal entry, which will document your plan for the week (Monday), your process (Tuesday to Thursday), and your evaluation of results (Friday). Please put newer entries above older ones.