IT PhD Computer Journal

In the fourth week of the CS50 (Harvard) course, we learned how to work with memory, which will help you perform a laboratory work on changing the volume of the sound in a .wav file using a program that receives the original music file and receives the value of the factor via the command line (how many times you need to change volume). So if the user enters a factor of 2, this means that the resulting file should become twice as loud (volume.c).

To complete this task, you need to take into account that the music file has a 44-byte header that contains metadata, and only after that there are 2-byte (16-bit) values ​​that describe the sounds. To overwrite a new file with a changed volume, you need to read and change the values ​​of each of the two bytes that describe the sound. To separate the header values, you can enter a new uint8_t header[44] data array, and write the rest of the values ​​into an int16_t buffer (these are two special types of variables that can then be used as an argument in the fread and fwrite functions).

Continue reading →

In the 4th week of the CS50 (Harvard) course, we studied the principles of working with memory and data arrays. We were faced with the task of writing a program that will apply filters to the original image (filter-less). You need to make 4 filters: black and white, sepia, specular and blur. The original picture is a 24-bit .BMP file, which means that each pixel of this picture contains 24-bit information that encodes an RGB color (8 bits are allocated for each individual color – red, green, blue).

The color encoding can be considered in hexadecimal as, for example, 0xff – which in decimal corresponds to 255 (if red is encoded this way, then 255 means “the most red”). Each image contains in its code not only the colors themselves, but also metadata in the header (14 bytes BITMAPFILEHEADER and 40 bytes BITMAPINFOHEADER). Immediately after the headers, color encoding in the bitmap begins. Given that a hexadecimal number encodes 4 bits, it would take two hexadecimal numbers to encode one color (eg red).

Continue reading →

An example of how addresses are stored in memory:

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

int main(void)
{
    int* x = NULL;

    printf ("address of new pointer-type variable x: %p\n", &x);
    printf ("value of variable x: %p\n", x);

    x = (int*) malloc(sizeof(int));

    printf ("now pointer-type variable x value exists and it is: %p\n", x);

    printf ("address of new pointer-type variable x: %p\n", &x);

    return 0;
}

A more complex example from cs50, which we analyzed in detail with the help of comments:
Continue reading →

A curious feature: howto swap numeric variables ezpz without a buffer using the bitwise XOR operation (bitwise exclusive OR):

#include <stdio.h>

int main(void)
{

    int a = 3;
    int b = 5;

    printf("a = %d, b = %d\n", a, b);
    a = a ^ b;
    // a   =   11
    // b   =  101
    // a^b =  110
    printf("a = %d, b = %d\n", a, b);
    b = a ^ b;
    // a   =  110
    // b   =  101
    // a^b =  011
    printf("a = %d, b = %d\n", a, b);
    a = a ^ b;
    // a   =  110
    // b   =  011
    // a^b =  101
    printf("a = %d, b = %d\n", a, b);

    return 0;
}

What the foo! 😀

We continue the course cs50, week three, sorting algorithms. It’s time for the lab. It is very simple:

• download test setup: https://cdn.cs50.net/2021/fall/labs/3/sort.zip
• inside the archive there are three already compiled C programs: sort1, sort2 and sort3 are binaries, i.e. binary code files, so we can’t view their C source code.
• each of these programs works on one of the sorting algorithms: selection sort, bubble sort, or merge sort. In what file what – we do not know. Our task is to determine which sorting algorithm is used in each binary..

Continue reading →

To learn recursion you need to pump up some muscles. To do so – make some of exercises  which are listed below. If something did not work out, you can peep the solution. Most likely the next day you will forget about the solution – so you can try to implement this exercise again. Recursion is a rather atypical task for the brain, so it’s good idea to repeat the same exercise several times. Solutions are below.

1. printing numbers from 1 to n
2. print even/odd numbers up to n
3. exponentiation of n
4. print n! (factorial is the product of numbers up to n)
5. printing the sum of numbers from n to m
6. printing Fibonacci numbers (each next is the sum of the previous two)
7. print Collatz numbers (even: n/2; odd: n*3+1)
8. copying a string from one to another
9. printing array elements
10. print line backwards
11. converting decimal to binary
12. binary search
13. bubble sort
14. merge sort

Continue reading →

We continue to take the Computer Science CS50 course and the C language. We study recursion using the example of the Collatz hypothesis – an interesting (and easy to understand) mathematical problem that has not yet been solved by scientists.

Collatz hypothesis:

1. Take any positive integer
2. If it’s even, then divide it by 2
3. If odd, then multiply by 3 and add 1 (we get n * 3 + 1).
4. Next, we evaluate the resulting number again – is it even or not, and again perform the same actions until we get 1.

In total, the essence of the Collatz conjecture is that absolutely any number, when these two simple operations are applied to it, will sooner or later turn into 1.

Continue reading →

In the third week of the Computer Science CS50 (Harvard) course, it is proposed to do homework in Problem Set 3 called runoff.c – you need to write a program code that does not just calculate which candidate received the most votes, like last time, in the runoff program you need to implement voting until more than 50% of the votes of all voters are collected.

The winner will be announced only when one of the candidates receives more than half of the votes. To do this, each voter ranks all candidates from highest preference (rank 1) to least preference (last rank). Next, the sum of votes in the first round (rank 1) is calculated. If one of the candidates receives more than 50% of the votes at this stage, he is declared the winner.

Continue reading →

The third week of Computer Science CS50 (Harvard) training begins and we continue to learn the C language. The first task: the implementation of a voting system where the candidate with the most votes wins, the so-called. plurality system or simply “winner takes all” (plurality.c). The user can choose one from the list of candidates and vote for him. When the votes are counted, the candidate with the most votes is declared the winner of the election.

Continue reading →

In the second week of the Computer Science CS50 (Harvard) course, after completing all the individual tasks, we move on to the C lab, which must be completed in a group. It will be an interesting task – to write the code for the game “Scrabble” (Scrabble.c). The essence of the task: the players come up with words that score a different number of points depending on the letters in this word, while each letter is assigned a different number of points from 1 to 10 and then these points are added up (the sum of the points of the letters gives the total number of points in the word).

For this task, the following table of correspondences of letters and points is used:

Continue reading →

We continue to do homework from Problem set 2 in Computer science CS50 (Harvard). Last time, we learned how to encrypt text by shifting letters by a certain number (key) entered by the user. And this time we will solve the problem more complicated, it will be the Substitution.c program and it also encrypts the text by replacing some letters with others according to the principle that the user enters on the command line when the program starts. This principle looks like a string of letters of the alphabet arranged in a reversed order, as in the example:

$ ./substitution JTREKYAVOGDXPSNCUIZLFBMWHQ
plaintext:  HELLO
ciphertext: VKXXN

Continue reading →

We continue to take the Computer Science CS50 (Harvard) course, and this time we will do the task of calculating the level of complexity of the text according to the Colman-Liau index (readability.c) in the C programming language. According to the idea of the two authors of the method, we can estimate the complexity of the text and thus distribute books by school grades (from simple texts, where the index is less than 1, to academically complex ones with an index greater than 16). The calculation is based on the formula:

index = 0.0588 * L - 0.296 * S - 15.8 ,
where L is the average number of letters per 100 words in the text,
S is the average number of sentences per 100 words in the text.
Continue reading →

We continue to do homework in the Computer science CS50 (Harvard) course, and this time we need to write the program code and encrypt a text message.

The essence of the ceasar.c task is that the program asks for the user’s text input, and then displays a line of text below in encrypted form with the user’s key. The key is specified when starting the program on the command line after naming the program itself argv[]. So in the example of running the finished program, the user enters the key = 13 and his text “Hello, world!”, and at the output he receives this text in the form of a cipher:

Continue reading →

While studying Greedy Algorithms at CS50 (Harvard), let’s solve the problem about coins (Cash.c). Let’s say you need to give change to a customer in a store and you want to minimize the number of coins you give out to each customer. If you are a cashier, then you have coins (25 cents), ten cents (10 cents), five cents (5 cents) and a penny (1 cent) in the cash register. How to decide which coins and how much to transfer to the buyer?

Imagine a “greedy” cashier who wants to get as big a chunk out of this problem as possible with every coin he takes out of the drawer. Suppose you owe the customer 42 cents, then the largest first coin you can take is 25 cents. This choice will reduce the amount to be given away to 17 cents, since 42 – 25 = 17. It turns out that with the help of smaller coins we will need to solve a smaller problem. This approach from largest to smallest will give the smallest possible number of coins in change.

Solution (Igroglaz):

Continue reading →

In the cs50 course (Harvard) there is a C programming problem to determine the correctness of a credit card number through the Luhn algorithm (credit.c). Let’s analyze this problem and show two more solutions.

So. Any credit card has a number printed on it, which is also stored in the database of the bank that issued the card. Credit card numbers are generated in such a way that they have some kind of “checksum” – a mathematical relationship between at least one number and others. This checksum allows you to quickly perform initial checks and detect typos on the client side without having to make a request to the server.

This is where the Luhn Algorithm (created by Hans Peter Lun of IBM) comes in handy, which allows you to check the validity of the card in this way:

Continue reading →

An interesting puzzle for beginners from CS50 (Harvard).

Task: draw a pyramid from the Mario (mario-less.c) game using # symbols (lattice or hash). The user is asked: “How many blocks to make a pyramid from?”, he enters a number and the pyramid is drawn, right-aligned, like this:

       #
      ##
     ###
    ####
   #####
  ######
 #######

igroglaz solution: Continue reading →