CSCI H343 Data Structures Fall 2023

Lecture: Course Introduction

In the beginning was the Tao. The Tao gave birth to Space and Time. Therefore Space and Time are the Yin and Yang of programming.

Programmers that do not comprehend the Tao are always running out of time and space for their programs. Programmers that comprehend the Tao have enough time and space to accomplish their goals.

How could it be otherwise? – The Tao of Programming

Introduce myself

Introduce course AI’s

Course web page, syllabus, schedule (due dates, etc.)

https://iudatastructurescourse.github.io/course-web-page-fall-2023/

Participation:

Suggested weekly schedule (4 credits * 3 = 12 hours of outside-class work)

Overview of course content

Software Tools

Project 1: Flood It!

Appetizer: The Maximum Subsequence Problem

Find the section of the Tecumseh Trail Marathon with the greatest net change in altitude. Show TecumsehMarathon.pdf.

change:   -25, -100, +100, -25,-75,-125,+100,+100,-25, +75,   -50, -100
			0     1     2    3   4    5    6    7   8    9   10    11

We want the contiguous subsequence with the largest sum. This is also known as the Maximum Subarray Problem.

Analysis of the time complexity:

The crossing-subarray is linear, that is, c * m where m is the size of the subarray.

Recursion tree:

                c*n                     = c*n
            /         \
       c*n/2          c*n/2             = c*n
      /    \          /    \
    c*n/4  c*n/4   c*n/4   c*n/4        = c*n
    ...

What’s the height?

At the bottom, at a leaf, we have n/(2^h) = 1. We want to solve for h, so we isolate the 2^h term on one side.

n = 2^h

Then we take the log of both sides. (Recall that log (2^x) = x for any x.)

log n = h

Total work is c * n * lg n, so the time for this divide-and conquer algorithm for maximum-subarray is is roughly

n lg n