Announcements

Friday, April 2, 2004

In question 1, part 2, it is node with the key value 6 has to be moved up.

Wednesday, Feb 15, 2004

In question 2, it should be "Programs 5.14 and 5.15" not "Prgrams 5.15 and 5.16)

Wednesday, Feb 4, 2004

Since we could not cover the sorting algorithms in the class last time- youneed not do Problem 3 for HW2
Problem 3 will be included in the HW3 - so if you finish early, start thinking about it.
Tentative date for Midterm is March 2 (will talk about it in next class)

Wednesday, Jan 28, 2004

Here is the starter for the post-fix caculator, if you are still stuck with the problem. Create the three files and then follow the instructions below.
I will provide more information regarding augmenting this with the infix-to-postfix conversion.

Header File STACK.h

typedef int Item;
void STACKinit(int);
int STACKempty();
void STACKput(Item);
Item STACKpop();

Implementation File STACK.c

#include <stdlib.h>
#include "STACK.h"
static Item *s;
static int N;
void STACKinit(int maxN)
{ s = malloc(maxN*sizeof(Item)); N = 0; }
int STACKempty()
{ return N == 0; }
void STACKpush(Item item)
{ s[N++] = item; }
Item STACKpop()
{ return s[--N]; }

Client Program File CLIENT.c

#include <stdio.h>
#include <string.h>
#include "STACK.h"
main(int argc, char *argv[])
{ char *a = argv[1]; int i, N = strlen(a);
    STACKinit(N);
    for (i = 0; i < N; i++)
      {
        if (a[i] == '+')
          STACKpush(STACKpop()+STACKpop());
        if (a[i] == '*')
          STACKpush(STACKpop()*STACKpop());
        if ((a[i] >= '0') && (a[i] <= '9'))
          STACKpush(0);
        while ((a[i] >= '0') && (a[i] <= '9'))
          STACKpush(10*STACKpop() + (a[i++]-'0'));
      }
    printf("%d \n", STACKpop());

You will run as follows using "gcc" or "cc":

> gcc STACK.c CLIENT.c -o calc
(the "-o calc" tells the compiler to create the executable file named "calc" - if you omit this part, the compiler will create executable file "a.out")

Then you can run your program as follows:

> calc "5 6 *"   (answer is 30)

("5 6 *" part is needed because the input to the program is stored as a string in argv[1])

Hope this makes things easier.

Modnay, Jan 26, 2004

The homeworks can be submitted by Midnight, Friday, Jan 30.
Do not hesitate to write to me if you have problems or come to meet me (not on Truesdays though)
In Problem 3 - you need to just to the evaluation - no need to do the conversion. Also note that the program in book requires that you input the post-fix expression in such as way that there is a space after an integer (read the description properly).

Wednesday, Jan 21, 2004

As, many of you received the textbook only recently, the deadline for the HW1 has been extended. You should submit your assigngments by midnight on Monday, Jan 26.

Friday, Jan 22, 2004 (Topic: HW1)

Linked List Exercise :

Q2.40 and Q2.43 for those who do not have a book (Q: Zhong Guo)

2.40 Solve the recurrence C(N) - C(N/2) + N^2 for N >= 2 C(1) = 0, and N is a power of 2 [In C(N), N is the subscript; N^2 means N to pwer 2)

2.43 Solve the recurrence C(N) - [C(N/2)]^2 for N >= 2 C(1) = 1, and N is a power of 2 [In C(N), N is the subscript)

Regarding what to implement (Q: Partha Ghosh)

You will the code given in link.h and link.c in the book.
You will create client.c with additional functions and the main() function.
In the client.c file, you will have an include statement to include the link.h file (as in example Program 3.13)
You will have to compile the two files client.c and list.c

To compile try: g++ client.c list.c -o client

Here, client is the executable file.

Please include approriate interaction feature to allow users to enter n numbers (Note: I have not mentioned this in the HW).

You can copy the book's code from the Sedgewick's homepage (Link to Resources from the course page).

Submission

Send all the program files and the solutions/answers files to the GSA

Wednesday, Jan 14, 2004

The HW1 has been posted.
Some links to useful resources has been also included in the main page.