Transcript Weekly Handout Number 1

Introduction and a Review of
Basic Concepts
• Syllabus and goals of the course
• Object oriented programming contrasting to C programming
– Objects, classes, methods
– Instantiation, references
– Polymorphism, inheritance
– Constructor, destructor, garbage collection
– Encapsulation
– Public, private, protected
• Data structures already introduced: Stacks, queues, linked lists
• Recursion and induction
Understanding data structures and algorithms is a major
difference separating computer scientists from one who reads a
manual and begins to program.
C versus Java
• The dot in Java is equivalent to the -> C; there is no Java
equivalent to the C dot operator. Generally, use -> in most cases
and declare variables using the ‘*’ (indicating pointer)
• There is no Boolean in C. Many programmers declare TRUE
and FALSE using #define
• C has no garbage collection. To avoid memory leaks, make sure
to free whatever you malloc.
• Use NULL in C, instead of the null in Java
• Use scanf for input, but make sure to clear the input buffer after
an error (scanf("%s*"))
• C has no methods (it has functions), so dot notation makes no
sense. Replace: object.method by function(data
• There is no length property in arrays and strings. Array sizes
must be stored in a separate variable.
• Be careful with pointers and memory management. C doesn’t
catch all errors at compile time.
Strings in C
• There is no String type, use an array of characters (char *data).
• C has no “+” operator for string concatenation. Use strcat, but make
sure you have an allocated area in memory to hold the larger string.
• To truncate a string, store '\0' in the appropriate index.
• To format output, use printf.
• For both puts and printf, make sure to follow the output with
fflush(stdout);. Otherwise, output only occurs when the accumulated
print buffer gets large enough.
• There are many string functions in C, all starting with str. There is also
memory manipulation functions, all starting with mem.
• Make sure your strings end with a null. Java has the length in the front
of a string; C has a null at the end.
Analysis of Algorithms
• Definition of Algorithm. Why study data types and algorithm?
– Step-by-step solution to a problem
– Often the problem can be specified in terms of the size of the data set (n).
• Algorithm performance (The technical term is complexity)
– A good algorithm implemented by a bad programmer will beat a bad
algorithm implemented by a good programmer
– A time function, f, of the dataset size is often used to measure
effectiveness as the data set size grows. For example, f(n) <= c*n, where
c is a constant > 0. Other examples of the growth rate are c*n2, c*lg n, c,
lg2 n, etc.
– Big Oh notation.
• How to determine if an algorithm is a good one?
–
–
–
–
How fast does it work on a given data set?
What is the Relationship between time and data set size?
How does it perform on different data set sizes?
Growth is more important than a given run’s performance
Big Oh Notation
Measurement of algorithm efficiency in
terms of memory or time as the problem size increases
• Formal Definition: f(n) = O(g(n)) means there are positive constants c
and z, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ z. The values of c and z
must be fixed for the function f and must not depend on n.
• Explanation of terms:
1.
2.
3.
4.
g(n) is a well known function to which we want to compare our
algorithm.
f(n) is how our algorithm performs on different size data sets
z is an integer. For all data set sizes smaller than z, we don’t consider
the algorithm’s efficiency
c is a positive constant . By multiplying g by this constant, all
functions with equal or smaller slopes will satisfy the Big Oh
definition requirements.
Review of logarithms. Conversion of logarithms Logn x = logq x / logq n
Time or memory
Pictorial View of Big Oh
z
Data set size
Allocate Unique Random Numbers
• Declare the free list
int freeList[MAX];
• Initialize the free list
for (i=0; i<MAX; i++) freeList[i] = i;
freeCount = MAX;
• Allocate an entry from the free list
– Find a random index into the free list:
index = (int)(rand() * freeCount);
– Get the value from the free list (key = freeList[index];)
– Replace the index with the last value in the freeList
freeList[index] = freeList[--freeCount];
• Release an entry back to the free list
– Put the value to the end of the free list
freeList[freeCount++] = key;
Abstract Data Type
A general-purpose data structure encapsulated from
the user through a well-defined set of operation
• Design
– Design the operations that are to be used
– Design the data structure to be used
• Examples (What operations? What data-structure?)
–
–
–
–
Java’s primitive floating point number
Stacks, queues, and linked lists.
To be covered: Trees, priority queues, hash tables, graphs.
Arrays (Ordered and Unordered)
• Array operations and complexities (insert, delete, find,
expand,sort,access,traverse)
• Advantages and disadvantages