Hi,
The gentleman's expenses IMO are really hard to believe. Columbia's expense listing should be your upper limit assuming you are single and are ok with living a modest (student) life.
The line items where you can still cut back are on the housing and board expenses. I am not sure if you are a NYC resident but if you aren't you can restrict the monthly room and board to $1200 per month by taking the school dorms. You can find cheaper ones too but the dorms are very close to the campus. That straight away saves over a $1000 per month from the official estimate. So a reduction of $9000.
You can buy international edition of books or issue them from library. There are multiple sources of buying/renting the international editions.
Your second year total will be lower because your mandatory fees will almost surely won't be charged and within 1 year you'd know how to optimize your lifestyle to a lower expense than year 1.
You can earn part-time but I don't think the earning will be worth the time and effort you will end up a) searching for them b) working towards them.
You should ideally go one semester without them and see if you feel you can take out time for them and apply for them from 2nd semester onwards.
How much and where can you work will depend on you visa status. If you are an international student, you will be limited to number of work hours and you can legally work only on campus jobs that pay between 8 to 20$ per hour. That in the best case IMO won't exceed $4000 per year.