Exercises1

Practice the C programming concepts you have learned in lecture: strings, structs, and pointers. Introduction to assert()

#include "ex1.h"

#include <stdio.h>
#include <string.h>

/* Returns the number of times LETTER appears in STR.
There are two different ways to iterate through a string.
1st way hint: strlen() may be useful
2nd way hint: all strings end in a null terminator */
int num_occurrences(char *str, char letter) {
  /* TODO: implement num_occurances */
  int cnt = 0;
  for (int i = 0; i < strlen(str); i++) {
    if (str[i] == letter) cnt++;
  }
  return cnt;
}

/* Populates DNA_SEQ with the number of times each nucleotide appears.
Each sequence will end with a NULL terminator and will have up to 20
nucleotides. All letters will be upper case. */
void compute_nucleotide_occurrences(DNA_sequence *dna_seq) {
  /* TODO: implement compute_nucleotide_occurances */
  (*dna_seq).A_count = 0, (*dna_seq).C_count = 0, (*dna_seq).G_count = 0,
  (*dna_seq).T_count = 0;
  for (int i = 0; i < strlen((*dna_seq).sequence); ++i) {
    if ((*dna_seq).sequence[i] == 'A')
      (*dna_seq).A_count++;
    else if ((*dna_seq).sequence[i] == 'C')
      (*dna_seq).C_count++;
    else if ((*dna_seq).sequence[i] == 'G')
      (*dna_seq).G_count++;
    else
      (*dna_seq).T_count++;
  }
  return;
}

Exercises2

Get familiar with basic GDB commands

#include "pwd_checker.h"

#include <assert.h>
#include <stdio.h>
#include <string.h>

/*
Password checker

Requirements:
- Password must be at least 10 characters
- Password must contain at least
    - 1 upper case letter
    - 1 lower case letter
    - 1 number
- Password cannot contain the person's first name or last name (case sensitive)

For the simplicity of this exercise:
- This is not the most efficient way to implement this program
- These functions do not perform any error checking
- You can assume that the first and last name will never be the empty string
*/

/* Returns true if the length of PASSWORD is at least 10, false otherwise */
bool check_length(const char *password) {
  int length = strlen(password);
  bool meets_len_req = (length >= 10);
  return meets_len_req;
}

/* Returns true if LETTER is in the range [LOWER, UPPER], false otherwise */
bool check_range(char letter, char lower, char upper) {
  bool is_in_range = (letter >= lower && letter <= upper);
  return is_in_range;
}

/* Returns true if PASSWORD contains at least one upper case letter, false
 * otherwise */
bool check_upper(const char *password) {
  while (*password != '\0') {
    bool is_in_range = check_range(*password, 'A', 'Z');
    if (is_in_range) {
      return true;
    }
    ++password;
  }
  return false;
}

/* Returns true if PASSWORD contains at least one lower case letter, false
 * otherwise */
bool check_lower(const char *password) {
  while (*password != '\0') {
    bool is_in_range = check_range(*password, 'a', 'z');
    if (is_in_range) {
      return true;
    }
    ++password;
  }
  return false;
}

/* Returns true if PASSWORD contains at least one number, false otherwise */
bool check_number(const char *password) {
  while (*password != '\0') {
    if (check_range(*password, '0', '9')) {
      return true;
    }
    ++password;
  }
  return false;
}

/* Returns true if the person's first and last name are NOT in the password,
 * false otherwise */
bool check_name(const char *first_name, const char *last_name,
                const char *password) {
  /* Type "man strstr" in your terminal to learn what strstr does!
      To exit the man pages, press 'q' */
  /* Hint: a NULL pointer will evaluate to False in a logical statement while a
     non-NULL pointer will evaluate to True */
  const char *first = strstr(password, first_name);
  const char *last = strstr(password, last_name);
  return !(first || last);
}

/* Returns true if PASSWORD meets the conditions specified above */
bool check_password(const char *first_name, const char *last_name,
                    const char *password) {
  bool length, upper, lower, number, name;
  lower = check_lower(password);
  length = check_length(password);
  name = check_name(first_name, last_name, password);
  number = check_number(password);
  upper = check_upper(password);
  return (lower && length && name && upper && number);
}

Exercises3

1. See an application of double pointers
2. Get more practice using gdb
3. Learn how to find the location of segfaults using gdb

#include "linked_list.h"

#include <stdio.h>
#include <stdlib.h>

/* returns a new node whose data is set to DATA and next is set to NULL */
Node *create_node(int data) {
  /* Don't worry about malloc yet! It is not in the scope of this lab */
  struct Node *new_node = malloc(sizeof(struct Node));
  if (new_node == NULL) {
    perror("Malloc failed\n");
  }
  new_node->data = data;
  new_node->next = NULL;
  return new_node;
}

/* Don't worry about free(), it is not in the scope of this lab */
/* Frees the list starting at HEAD */
void free_list(Node *head) {
  while (head != NULL) {
    Node *temp = head->next;
    free(head);
    head = temp;
  }
}

/* Creates a new node whose data is set to DATA and adds it to the front of the
   list pointed to by HEAD.
   This function is heavily commented for instructional purposes. Please
   never use this many comments when you are writing code. */
void add_to_front(struct Node **head, int data) {
  /* Check if the head is NULL to make sure that we do not dereference a NULL
  pointer because that would result in a segfault */
  if (head == NULL) return;
  struct Node *new_node = create_node(data);
  if (*head != NULL) {
    /* The list is not empty */
    /* The new node's next should point to the head */
    new_node->next = *head;
  }
  /* We must set HEAD using the following line in order to change the original
   * list */
  *head = new_node;
  /* The following line would not work because it would only change our local
   * copy of HEAD */
  /* head = new_node */
}

/* Prints out a linked list starting at HEAD */
void print_list(struct Node *head) {
  struct Node *curr;
  for (curr = head; curr != NULL; curr = curr->next) {
    printf("%d->", curr->data);
  }
  printf("NULL\n");
}

/* Iteratively reverses a linked list whose first node is HEAD */
void reverse_list(struct Node **head) {
  if (head == NULL || *head == NULL) {
    return;
  }
  struct Node *curr = *head;
  struct Node *next = (*head)->next;
  curr->next = NULL;
  while (next != NULL) {
    struct Node *temp = next->next;
    next->next = curr;
    curr = next;
    next = temp;
  }
  *head = curr;
}

/* Creates a new node with a data field set to DATA and adds the node
   to the back of the list pointed to by HEAD */
void add_to_back(Node **head, int data) {
  if (head == NULL) {
    return;
  } else if ((*head) == NULL) {
    *head = create_node(data);
    return;
  }
  Node *new_node = create_node(data);
  Node *prev;
  for (Node *curr = *head; curr != NULL; curr = curr->next) {
    prev = curr;
  }
  prev->next = new_node;
}

Exercises4

1. Start with two pointers at the head of the list. One will be called fast_ptr and the other will be called slow_ptr.
2. Advance fast_ptr by two nodes. If this is not possible because of a null pointer, we have found the end of the list, and therefore the list is acyclic.
3. Advance slow_ptr by one node. (A null pointer check is unnecessary. Why?)
4. If the fast_ptr and slow_ptr ever point to the same node, the list is cyclic. Otherwise, go back to step 2.

#include "ll_cycle.h"

#include <stddef.h>

int ll_has_cycle(node *head) {
  /* TODO: Implement ll_has_cycle */
  if (head == NULL || head->next == NULL) return 0;
  node *slow = head, *fast = head;
  while (fast && fast->next) {
    fast = fast->next->next;
    slow = slow->next;
    if (slow == fast) return 1;
  }
  return 0;
}